삽입정렬Insertion Sort

삽입정렬Insertion Sort알고리즘의 특징

**gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html 많은부분 참고했습니다.

• 손안의 카드를정렬하는 방법과 유사.

• 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아서 삽입한다. 

• 매순서마다 원소를 삽입할 수 있는 위치를 찾아서 해당 위치에 넣는다. 

  • 두번째 자료(index = 1 )부터 시작한다

  • 1번째 값이 0번째값보다 작으면 1번째 값을 0번째에 넣고 0번째 값을 1번째 자리에 넣는다.

  • 여기까지하면 인덱스 0,1이 정렬된 자료가된다. 

  • 2번째 값을 0,1번째 값과 비교한후 적절한 자리에 넣고 해당 자리의원소들은 뒤로 한칸씩 밀린다. 

  • 여기까지하면 인덱스 0,1,2가 정렬된 자료가 된다. 

  • 3번째 값을 정렬된 자료와 비교하여 적절한 자리에 넣고 원래 자리에있던 원소들은 한칸씩 뒤로간다. 

  • 여기까지하면 0,1,2,3이 정렬된 자료가된다. 

  • n까지 반복하면 0부터 n까지 정렬이 완료된다.

• 장점

  • 안정한 정렬방법이다.
  • 자료의 수가 적을경우 알고리즘이 매우 간단하다. 
  • 대부분 정렬이 된 상태일경우 효율적이다. 

• 단점

  • 자료의 이동이 많다. 
  • 자료가 많은 경우 적절하지못하다. 

알고리즘 예제

31      25     12    22     11 처음 상태.
31     [25]    12    22    11 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25> 31    [12]    22    11 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12> 25    31    [22]    11 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12    <22>  25    31    [11] 마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11>    12    22    25    31 종료.}

삽입정렬Insertion Sort 코틀린 코드

fun insertionSort(arr: IntArray) : IntArray{
    var j = 0
    var key = 0


    for (i in 1 until arr.size) { //0번째 자료는 정렬된것으로 간주한다.
        key = arr[i]

        j = i
        while (--j >= 0 && key < arr[j]) {
            arr[j+1] = arr[j]
            arr[j] = key
        }


    }

    return arr
}

• 시간복잡도
  • 최선의경우
    • 비교횟수
      • 이동이 없이 1번의 비교만 이루어진다.
    • O(n)
  • 최악의 경우
    • 비교횟수
      • 모든 자료를 비교해야하기때문에 n개의 자료를 정렬할경우 n, n-1, n-2 ... 1 번의 비교를해야한다.
      • 비교는 O(n^2)번이라고할 수 있다.  
    • 교환횟수
      • 매번 교환이 이루어지기때문에 n, n-1, n-2 ... 1번의 교환이이루어진다. 
      • 교환이 O(n^2)번 이루어진다고할 수 있다.
    • 시간복잡도
      • O(n^2)

버블 정렬Bubble Sort

버블 정렬Bubble Sort 알고리즘의 특징

• 인접한 두 원소를 검사하여 정렬하는방법

• 느리지만 코드가 간단하여 자주 사용된다.(라고는 하는데 개인적으로 학부때 수업들을때말고는 사용해본적이 없긴하다.)

• 프로세스 방법

  • 인덱스 0 과 인덱스 1의 값을 비교한다.

  • 0번째의 값이 1번째의 값보다 크다면 스왑 한다.

  • 인덱스1과 인덱스 2의 값을 비교한다.

  • 1번째의 값이 2번째의 값보다 크다면 스왑 한다.

  • 인덱스를 증가시키면서 n 까지 반복한다.

  • n까지 반복하면 가장 큰 값이 맨 n에 위치하게된다.

  • 이제 인덱스 0부터 n-1 까지 반복한다.

  • 하나의 원소만 남을때까지 위의 과정을 반복한다.

• 장점

  • 구현이 단순하다. 

• 단점

  • 속도가 느리다.

알고리즘 예제

매우 적절할 버블정렬을 춤으로 나타낸 동영상이다.

youtu.be/lyZQPjUT5B4

버블 정렬Bubble Sort 코틀린 코드

fun bubbleSort(arr: IntArray): IntArray{
   var temp = 0
   for(i in arr.indices){
       for(j in 1 until arr.size - i)
           if(arr[j] < arr[j-1]) {
               temp = arr[j]
               arr[j] = arr[j - 1]
               arr[j - 1] = temp
           }
       }
    return arr
}

• 시간복잡도
  • O(n^2)
  • 정렬할 자료의 길이만큼 이중 반복을한다.

선택 정렬Selection Sort

선택 정렬Selection Sort 알고리즘의 특징

• 제자리 정렬(in-place sorting)의 하나이다.
  • 입력벼열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법.
• 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘.
  • 첫번째 순서에 첫번째 위치에 가장 최소값을 넣는다.
  • 두번째 위치엔 남은값중 최솟값을 넣는다.
  • n 번째 위치엔 남은 값중 최솟값을 넣는다.
• 프로세스 방법
  • 주어진 배열에서 최솟값을 찾는다.
  • 그 값을 맨앞의 값과 교체한다.
  • 맨처음 위치를 뺀 나머지 리스트를 같은 방법으로 교채한다.
  • 하나의 원소만 남을때까지 위의 과정을 반복한다.
• 장점
  • 자료의 이동 횟수가 미리 결정된다.
• 단점
  • 안정성을 만족하지않는다.

알고리즘 예제

선택정렬의 코틀린 코드

fun main(){

    print(selectionSort(intArrayOf(3,6,1,7,5,4,9)).joinToString(","))
    //1,3,4,5,6,7,9
}

fun selectionSort(arr: IntArray): IntArray{
   var minIdx = 0
   var temp = 0
   for(i in arr.indices){
       minIdx = i
       for(j in i+1 until arr.size   ){
          if(arr[minIdx] > arr[j]) {
              minIdx = j
          }
       }

       if(minIdx != i){
           temp = arr[i]
           arr[i] = arr[minIdx]
           arr[minIdx] = temp
       }

   }

    return arr
}

• 시간복잡도
  • O(n^2)
  • 정렬할 자료의 길이만큼 이중 반복을한다.