정렬 알고리즘(버블, 선택, 삽입, 퀵, 병합, 기수)

4-1 버블정렬

• 데이터의 인접 요소끼리 비교하고, swap연산을 수행하여 정렬하는 방식

 

# import sys
# input = sys.stdin.readline
n = int(input())
number = []

for i in range(n):
    i = int(input())
    number.append(i)

for j in range(len(number), 1, -1):
    for i in range(len(number[:j])-1):
        print(number[:j], j, i)
        if number[i] > number[i+1]:
            number[i], number[i+1] = number[i+1], number[i]  

print(number)

4-2 선택정렬

• 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식

 

# import sys
# input = sys.stdin.readline

n = list(map(int, input()))

for i in range(len(n)):
    max = i
    for j in range(i+1, len(n)):
        if n[j] > n[max]:
            max = j
    if n[i] < n[max]:
        n[i], n[max] = n[max],  n[i]

a = "".join(list(map(str, n)))
print(a)

4-3 삽입정렬

• 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식

# import sys
# input = sys.stdin.readline

n = list(map(int, input()))

for i in range(1, len(n)):
    insert_p = i
    insert_val = n
    for j in range(i-1, -1, -1):
        if n[j] < [i]:
            insert_p = j+1
            break
        if j==0:
            insert_p = 0
    for j in range(i, insert_p, -1):
        n[j] = n[j-1]
    a[insert_p] = insert_val

4-4 퀵정렬

• pivot값을 선정해 해당 값을 기준으로 정렬하는 방식

# import sys
# input = sys.stdin.readline

n, k = map(int, input().split)
a = list(map(int, input().split))

def quicksort(s, e, k):
    global a
    if s < e :
        pivot = partition(s, e)

        if pivot == k:
            return
        elif k <pivot:
            quicksort(s, pivot-1, k)
        else:
            quicksort(pivot+1, e, k)
def partition(s, e):
    global a

    if s+1 == e:
        if a[s] > a[e]:
            a[s], a[e] = a[e], a[s]
        return e
    m = (s+e) // 2
    s, m = m, s
    pivot = a[s]
    i = s+1
    j=e

    while i<=j:
        while pivot < a[j] and j>0:
            j -= 1
        while pivot > a[i] and len(a)-1:
            i += 1
        if i<=j:
            i, j = j, i
            i += 1
            j -= 1
    a[s] = a[j]
    a[j] = pivot
    return j

quicksort(0, n-1, k-1)
print(a[k-1])

4-5 병합정렬

• 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식

# import sys
# input = sys.stdin.readline
# print = sys.stdout.write

def merge_sort(s, e):
    if e-s < 1: return 
    m = s+(e-s)//2
    merge_sort(s, m)
    merge_sort(m+1, e)
    for i in range(s, e+1):
        tmp[i] = a[i]
    k = s
    index1 = s
    index2 = m+1

    while index1<=m and index2 <= 3:
        if tmp[index1] > tmp[index2]:
            a[k] = tmp[index2]
            k += 1
            index2 += 1
        else:
            a[k] = tmp[index1]
            k += 1
            index1 += 1
    while index1 <= m:
        a[k] = tmp[index1]
        k += 1
        index1 += 1
    while index1 <= m:
        a[k] = tmp[index1]
        k += 1
        index1 += 1
    while index2 <= e:
        a[k] = tmp[index2]
        k+= 1
        index2 += 1

n=int(input())
a = [0]*int(n+1)
tmp = [0]* int(n+1)

for i in range(1, n+1):
    a[i] = int(input())

merge_sort(1, n)

print(a)

4-6 기수정렬

• 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

•   # import sys
    # input = sys.stdin.readline
  
    n = int(input())
    count = [0]*10001
  
    for i in range(n):
        count[int(input())] += 1
  
    for i in range(10001):
        if count[i] != 0:
            for _ in range(count[i]):
                print(i)