4: 알고리즘-5(선택 정렬:Selection Sort)

선택 정렬(selection sort)

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가함

---

정렬되지 않은 숫자들을 오름차순 정렬하기

 

3 5 1 6 4 8 7

1 5 3 6 4 8 7

1 3 5 6 4 8 7

1 3 4 6 5 8 7

1 3 4 5 6 8 7

1 3 4 5 6 7 8

 

• 아래 숫자 중에서 가장 작은 값을 찾고 첫 번째 값과 교환한 다음 작은 숫자부터 시작해서 계속 바꿔줌
• 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지 와 차례대로 비교하여 그중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.
  

---

선택 정렬을 의사코드로 나타내기

 

For i from 0 to n-1
//n개의 항목이 있다면 첫 번째 항목은 0번째라고 하고 마지막 항목을 n-1째라고 함
    Find smallest item between i'th item and last item
    //i번째부터 마지막 항목 중 가장 작은 항목을 찾고
    Swap smallest item with i'th item
    // 그 가장 작은 항목을 i번째 항목과 교환하기

 

• 컴퓨터는 0부터 n-1을 1부터 n까지 세기 위해 사용함. 
• 첫 번째 과정에서 모든 항목을 다 살펴봄, 즉 제일 작은 수를 찾는 데 거의 n번의 과정이 필요함
• 이렇게 계속 진행하면 n번으로 시작해서 n-1번을 더하고 n-2번 계속 더해서 배열의 마지막에는 n(n+1)/2라는 관계식이 성립함 → (n^2+n)/2 → (n^2)/2 + n/2
• 버블 정렬 실행 시간의 상한을 Big O로 나타내면 O(n^2)이라고 할 수 있음(선택 정렬과 같이 n^2이 가장 빠르게 증가하기 때문)
• 프로그램을 배열 속 다른 값을 전부 보기 전까지 알 수 없기 때문에 버블 정렬 실행 시간의 하한도 똑같이 Ω(n^20가 됨(제일 작은 값이 맞는지 다 비교해야 함)
  

 

---

실행시간을 나타내기 위해 사용되는 Big O 표기

 

O(n^2): 버블정렬, 선택정렬

O(n log n)

O(n): 선형검색

O(log n): 이진검색

O(1)

---

실행시간을 나타내기 위해 사용되는 Big Ω 표기

 

Ω(n^2): 버블정렬, 선택정렬

Ω(n log n)

Ω(n):배열안에 존재하는 값의 개수 세기

Ω(log n)

Ω(1): 선형검색, 이진검색

 

 

https://everysmallstep.tistory.com/25

4: 알고리즘-2(알고리즘 표기법)

https://www.boostcourse.org/cs112/joinLectures/41307

모두를 위한 컴퓨터 과학 (CS50 2019)

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog