[제로베이스] CH3. 알고리즘 - 버블정렬, 삽입정렬, 선택정렬

버블정렬

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다. 원소를 정렬하는 모습이 마침 거품이 올라오는 모습같다고 해서 붙여진 이름이다.

list = [7,9,5,1,3,8,4,2,6]
length = len(list)-1

for i in range(length):
    for j in range(length-i):
        if (list[j] > list[j+1]):
            tmp = list[j+1]
            list[j+1] = list[j]
            list[j] = tmp

삽입정렬

정렬되어 있는 자료 배열과 비교해서, 알맞은 정렬 위치를 찾아 삽입하는 방법이다. 새로 넣을 원소를 기존의 정렬된 원소들 사이에서 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 합니다.

list = [1,7,9,5,3,8,4,2,6]
length = len(list)

for i in range(1,length):
    tmp = list[i]
    for j in range(i-1,-1,-1):
        if (list[j] > tmp):
            list[j+1] = list[j]
        else:
            list[j+1] = tmp
            break

선택정렬

정렬되지 않은 배열의 최대값(최소값)을 검색하여 배열의 오른쪽(왼쪽)부터 순차적으로 정렬을 반복하는 정렬 알고리즘이다. 배열이 미정렬 상태이므로 최소값 검색에는 이진 검색이 아닌 선형 검색 알고리즘을 사용한다.

list = [5,7,9,1,3,8,4,2,6]
length = len(list)

for i in range(length):
    minIdx = i
    for j in range(i+1,length):
        if (list[minIdx] > list[j]):
            minIdx = j
    
    tmp = list[minIdx]
    list[minIdx] = list[i]
    list[i] = tmp