버블 정렬Bubble Sort

버블 정렬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)
  • 정렬할 자료의 길이만큼 이중 반복을한다.