알고리즘 - Sort 정렬 (Selection sort, Insertion sort, Bubble sort), Python 코드

Sort (정렬)

n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘

 

Sort 알고리즘 종류

1. Selection sort
2. Insertion sort
3. Bubble sort
4. Merge sort
5. Quick sort

기초적인 정렬 알고리즘

평균적으로 O(n^2)의 시간이 소요되는 정렬 알고리즘

- Selection sort (선택정렬)

- Insertion sort (삽입정렬)

- Bubble sort (버블정렬)

 

고급 정렬 알고리즘 

평균적으로 O(nlogn)의 시간이 소요되는 정렬 알고리즘

- Merge sort (병합정렬)

- Quick sort (퀵정렬)

- Heap sort (힙정렬)

 

 

Selection sort (선택정렬)

- 제자리 정렬 알고리즘

- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

 

[과정]

1. 주어진 배열 중에서 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

Selection sort 알고리즘의 특징

장점 : 자료 이동 횟수가 미리 결정된다.

단점 : 안전성을 만족하지 않음

 

 

Python으로 나타낸 Selection sort

#best : n^2
#avg : n^2
#worst : n^2
def selection_sort(arr) :
    for i in range(len(arr)-1) :
        min_idx = i
        for j in range(i+1, len(arr)) :
            if arr[j] < arr[min_idx] :
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

 

 

 

 

Insertion sort (삽입정렬)

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

- 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하며 삽입 위치를 지정한다. 

- 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

 

Insertion sort 알고리즘의 특징

장점 : 안전한 정렬 방법이며, 레코드가 어느정도 정렬되어 있는 경우 효율적이다. 

단점 : 레코드의 양이 많거나, 크기가 클 경우에는 적합하지 않다. 

 

 

Python으로 나타낸 Insertion sort

#best : n
#avg : n^2
#worst : n^2

def insertion_sort(arr) :
    for end in range(1, len(arr)) :
        for i in range(end, 0, -1) :
            if(arr[i-1] > arr[i]) :
                arr[i-1], arr[i] = arr[i], arr[i-1]

 

 

 

Bubble sort (버블정렬)

- 서로 인접한 두 원소를 비교하며 정렬하는 알고리즘

- 왼쪽부터 시작하여 이웃한 쌍들을 비교해 나간다. 순서대로 되어 있지 않으면 자리를 바꾼다. 

- 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외된다. 이를 반복함

 

Bubble sort 알고리즘의 특징

장점 : 구현이 매우 간단함

단점 : 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.

 

 

Python으로 나타낸 Bubble sort 

#best : n^2
#avg : n^2
#worst : n^2
def bubble_sort(arr, n) :
    for i in range(n-1, 0) :
        for j in range(i) :
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

 

 

 

 

 

 

 

 

 

 

[퀵, 병합 정렬]

2023.04.05 - [알고리즘] - 알고리즘 - Sort 정렬 (Selection sort, Insertion sort, Bubble sort), Python 코드

알고리즘 - Sort 정렬 (Selection sort, Insertion sort, Bubble sort), Python 코드