정렬 알고리즘

버블정렬(Bubble Sort)

1. 배열의 i번째 인덱스와 i+1번째 인덱스의 값을 비교한다.
2. i번째 인덱스의 값이 더 크다면 자리를 상호 교환(swap)한다.
3. 위 과정을 반복수행한다.

※ 시간 복잡도 O(N^2) → 시간 효율이 좋지 않다

LIST = [7,4,5,6,2,9,8,1,3]

for i in range(len(LIST)-1):
	for j in range(len(LIST)-1-i):
    	if LIST[j] > LIST[j+1]:
        	LIST[j], LIST[j+1] = LIST[j+1], LIST[j]
	print(LIST)
===========================
[4, 5, 6, 2, 7, 8, 1, 3, 9]
[4, 5, 2, 6, 7, 1, 3, 8, 9]
[4, 2, 5, 6, 1, 3, 7, 8, 9]
[2, 4, 5, 1, 3, 6, 7, 8, 9]
[2, 4, 1, 3, 5, 6, 7, 8, 9]
[2, 1, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9] ←

삽입정렬(Insertion Sort)

1. 배열의 1번째부터 n번째까지 차례대로 원소를 꺼낸다.
   꺼낸 원소의 값과, 원소의 이전 위치의 값들을 차례대로 비교한다.
2. 원소 값보다 비교하는 값이 더 클 경우, 비교하는 값을 오른쪽으로 한 칸 이동시키고 비교할 인덱스의 값을 하나 감소시킨다.
3. 위의 과정을 계속 반복하다가 비교할 인덱스가 0보다 작아지거나, 비교하는 원소가 기존 원소와 같거나 작아지면 반복을 마친다.

※ 시간 복잡도 O(N^2)

LIST = [7,4,5,6,2,9,8,1,3]

for i in range(1, len(LIST)):
    for j in range(i, 0, -1):
        if LIST[j-1] > LIST[j]:
            LIST[j-1], LIST[j] = LIST[j], LIST[j-1]
    print(LIST[:i+1])
===========================
[4, 7]
[4, 5, 7]
[4, 5, 6, 7]
[2, 4, 5, 6, 7]
[2, 4, 5, 6, 7, 9]
[2, 4, 5, 6, 7, 8, 9]
[1, 2, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9] ←

선택정렬(Selection Sort)

한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞과 교환하는 방식의 정렬

※ 시간 복잡도 O(N^2)

LIST = [7,4,5,6,2,9,8,1,3]

for i in range(len(LIST)):
    min_index = i
    for j in range(i+1, len(LIST)):
        if LIST[min_index] > LIST[j]:
            min_index = j
    LIST[i], LIST[min_index] = LIST[min_index], LIST[i]
    print(LIST[:i+1])
===========================
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9] ←