[알고리즘] 기본정렬

버블 정렬

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

코드

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

로직

1. len(arr) - 1 만큼 반복
2. 반복문 안에서 len(arr) - index - 1 만큼 반복
3. 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 swap
4. swap이 한번도 일어나지 않았다면, break

• swap이 일어나지 않았으면 이미 정렬되어 있는 리스트라서, 반복문을 끝낸다.
• 한 번 반복문을 실행할 때마다 리스트 마지막에 가장 큰 수가 정렬되기 때문에, 그 개수만큼 이중 반복문에서 덜 반복한다.

시간 복잡도

O(n^2)

• n만큼 반복문을 2번 사용하기 때문

---

삽입 정렬

• 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

코드

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2 - 1] > data[index2]:
                data[index2 - 1], data[index2] = data[index2], data[index2 - 1]
            else:
                break
    return data

로직

1. 배열길이-1 만큼 반복문
2. 두 번째 인덱스부터 시작
3. 당 인덱스 앞에 있는 인덱스 값과 비교해서 더 작으면, swap
   • 이를 더 작은 데이터를 만날 때까지 반복한다.
   • 더 작은 데이터를 만나면 반복문을 끝낸다.

시간 복잡도

O(n^2)

• 반복문이 두 개이기 때문

---

선택 정렬

아래와 같은 순서를 반복하며 정렬하는 알고리즘

코드

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data

로직

1. 주어진 데이터 중, 최소값을 찾음
2. 해당 최소값을 맨 앞의 값과 바꿈
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

시간 복잡도

O(n^2)

• 반복문이 두 개이기 때문