기본적인 정렬 알고리즘

simple, slow - Bubble sort, Insertion sort, Selection sort

fast - Quick sort, Merge sort, Heap sort

O(N) - Radix sort

selection sort

29 10 14 37 13 중에서 가장 큰 값을 찾는다. 이 값을 맨 마지막 자리와 바꾼다. 맨 마지막 자리를 제외한 나머지 수 중에 가장 큰 수를 맨 뒤에 넣는다. 반복한다.

data=[29,10,14,37,13]
for i in range(4,0,-1):
    m = max(data[:i+1])
    data[i],data[data.index(m)] = m,data[i]
print(data)

수행시간:

for문은 n-1번 반복, 가장 큰 수를 찾기 위한 비교 횟수 n-1,n-2,n-3,...,2,1 교환은 상수시간

시간 복잡도 T(n) = (n-1)+(n-2)+...+2+1=O(n^2)

(n-1)*n/2 이므로 최악, 최선, 평균 시간 복잡도가 동일하다.

bubble sort

selection sort와 비슷해보인다. 방법에 있어 약간 차이가 있다. 첫번째 인덱스부터 시작에서 다음 인덱스보다 크면 자리를 바꾸고 작으면 냅둔다. 인덱스를 이동하면서 반복한다. 전체 리스트의 길이는 줄면서 인덱스 0부터 끝까지 돌아야한다.

data=[29,10,14,37,13]
for i in range(4,0,-1):
    for j in range(i):
        if data[j]>data[j+1]:data[j],data[j+1] = data[j+1],data[j]
print(data)

수행시간:

for문은 n-1번 반복, for는 각각 n-1,n-2,n-3,...,2,1번 반복, 교환은 상수 시간 작업

T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

insertion sort

15 12 13 10 14 11

12 15 13 10 14 11

12 13 15 10 14 11

이런 식으로 인덱스를 0부터 끝까지 돌리면서 알맞은 자리에 넣어야 한다. 앞에서부터 정렬하면 뒤에 있는건 모조리 한칸씩 밀어야해서 시간 복잡도가 증가한다. 뒤에서부터 정렬을 해야한다. 뒤에서부터 하면 어차피 옮겨져야 할 값들이 뒤로 밀리면서 알맞은 자리를 찾아갈 수 있게 된다.

for문의 i는 인덱스 1부터 끝까지 돈다. 해당 인덱스의 원소는 변수 temp에 저장하고 while문의 j는 i보다 1작은 곳에서 시작한다. 즉 i의 인덱스는 계속 증가하면서 j는 i의 영향을 받으며 i보다 1 작은 인덱스에서 0까지 도는 것이다. i가 커지면서 j는 뒤에서부터 0까지 간다.

인덱스 j의 원소가 temp보다 크다면 이를 뒤 칸으로 밀어준다. 계속 밀어주다가 temp보다 크지 않은 수가 나오면 while문을 종료한다. 이때 data[j]는 temp보다 작거나 같은 수이다. 그러므로 data[j]에 temp를 넣는 것이 아닌 바로 뒤인 data[j+1]에 temp를 넣어준다.

data=[15,12,13,10,14,11]
for i in range(1,6):
    temp = data[i]
    j=i-1
    while j>=0 and data[j]>temp:
        data[j+1]=data[j]
        j-=1
    data[j+1]=temp
print(data)

수행시간:

for문은 n-1번 반복, 삽입은 최악의 경우 i-1번 비교

최악의 경우 T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)