자료구조 이론 :) 선택정렬, 버블정렬, 삽입정렬을 알아보자

goal

선택정렬, 버블정렬, 삽입정렬을 이해한다.

1 ] 선택정렬(Selection Sort)

선택 정렬은 해당 자리를 이미 선택하고 그 자리에 오는 값을 찾는 것이다.

※ 선택정렬은 제자리 정렬(in-place sorting) 알고리즘의 하나이다.

제자리 정렬이란, 입력 배열(정렬되지 않은 값들)이회에 다른 추가 메모리를 요구하지 않는 정렬 방법이며

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

1. 선택정렬의 과정

해당 과정은 선택정렬을 이용하여 배열을 오름차순으로 표현하는 과정을 나타낸다.

 

1. 선택정렬을 이용하여 배열을 오름차순으로 표현하는 과정 말로 표현하기

• N번째 인덱스를 고정시킨다. ....(1)
• N번째 인덱스와 이후의 인덱스들과의 값을 비교한다. ....(2)
• 만약, 최소값이 이후의 인덱스이면 값을 교체한다. ....(3)
• (1), (2), (3)과정을 N-1번째 인덱스를 가리킬때까지 반복한다.

 

2. 선택정렬의 장점

• 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, 버블정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• 버블정렬과 마찬가지로 배열 내부에서 자료값이 교환되기 때문에 다른 메모리 공간을 필요로 하지 않는다.

 

3. 선택정렬의 단점

• 불안정 정렬(Unstable Sort)이다.

 

4. 선택정렬의 시간복잡도

• O(n^2)

 

5. 선택정렬의 공간복잡도

• O(n)

 

---

2 ] 버블정렬(Bubble Sort)

버블정렬은 배열의 인접한 두 개의 index를 비교하여 더 큰 숫자를 뒤로 보내 차곡차곡 쌓아 정렬하는 방식이다.

결론적으로 배열의 뒷쪽부터 정렬하는 방법이라 생각하자.

1. 버블정렬의 장점

• 구현이 매우 간단하고 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식으로, 다른 메모리 공간을 필요하지 않는다. (제자리 정렬)
• 안정 정렬(Stable Sort)이다.

 

2. 버블정렬의 단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 굉장히 비효율적이다.
• 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

 

3. 버블정렬의 시간복잡도

• O(n^2)

 

4. 버블정렬의 공간복잡도

• O(n)

---

3 ] 삽입정렬(Insertion sort)

삽입정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 십입하는 것이다. 0번째 인덱스의 앞쪽에는 숫자가 없기 때문에 정렬의 시작은 1번째 인덱스로 시작한다.

1. 삽입정렬의 시간복잡도

• Best T(n) = O(n)
• Worst T(n) = O(n^2)

최악의 시간복잡도를 가지는 경우는 입력 자료가 역순인 경우가 되겠다.

최선의 경우는 이동 없이 1번의 비교만 이루어진다. (외부 루프 : (n-1)번 )

 

2. 삽입정렬의 공간복잡도

• O(n)

 

3. 삽입정렬의 장점

• 알고리즘이 단순
• 원소가 정렬된 경우 효율적일 수 있다.
• 정렬하고자 하는 배열 안에서 교환되는 방식이므로 다른 메모리 공간을 필요하지 않는다. (제자리 정렬)
• 안정 정렬이다.
• 삽입정렬은 선택정렬과 버블정렬에 비해서 상대적으로 빠르다.