[자료구조] Selection Sort ( with pseudo code) 해보기.

Selection Sort Example

 

배열 A[0...6]에 들어 있는 7개의 정수를 오름차순으로 정렬하기.

---

Overview of Algorithm for n integers in A[0...n-1]

 

    * 배열을 2개의 리스트로 나눈다. 

        -  A[0], ... , A[i-1] : 정렬된 리스트 // 처음에는 비어있다.

        -  A[i], ... , A[n-1] : 정렬되지 않은 리스트 // 처음에 i = 0이다.

 

    * 정렬되지 않은 리스트 A[i], ... , A[n-1]에서 최솟값을 찾아낸다.

        -  먼저, A[i]을 최솟값이라 가정한다.

        -  A[i+1], ... , A[n-1]에서 A[i]보다 작은 값이 있는지 찾아본다.

 

    * A[i]와 최솟값의 자리를 바꾼다.

        -  A[0], ... , A[i] : 정렬된 리스트 

        -  A[i+1], ... , A[n-1] : 정렬되지 않은 리스트

 

    * 정렬이 끝날 때 까지 반복한다.

        -  i = n-2가 될때 까지. 마지막 하나는 굳이 정렬하지 않아도 됨.

---

Selection sort pseudo code

for i <- 0 to n-2 do{
    min <- i
    for j <- i+1 to n-1 do{         // unsorted list A[i+1]...A[n-1]
        if(A[j]<A[min]) min <- j    // A[j]가 A[min]보다 작다면 min을 j로 덮어씌우고 for문을 지속한다.
    }
    swap(A[i], A[min])              // 최종적인 최솟값 A[min]와 A[i]의 값을 바꿈
}                                   // 이 과정을 반복하면 정렬이 됨.

출처

CAU DBLab

https://intellipaat.com/blog/tutorial/python-tutorial/data-structures-with-python-cheat-sheet/