버블정렬

버블정렬(bubble sort)이란?

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

• 데이터가 네 개 일때, 예시
  • ex) unSortedArray = [1, 9, 3, 2]
    • 1차 로직 적용
      • 1 와 9 비교, 자리바꿈없음 [1, 9, 3, 2]
      • 9 와 3 비교, 자리바꿈 [1, 3, 9, 2]
      • 9 와 2 비교, 자리바꿈 [1, 3, 2, 9]
    • 2차 로직 적용
      • 1 와 3 비교, 자리바꿈없음 [1, 3, 2, 9]
      • 3 과 2 비교, 자리바꿈 [1, 2, 3, 9]
      • 3 와 9 비교, 자리바꿈없음 [1, 2, 3, 9]
    • 3차 로직 적용
      • 1 과 2 비교, 자리바꿈없음 [1, 2, 3, 9]
      • 2 과 3 비교, 자리바꿈없음 [1, 2, 3, 9]
      • 3 과 9 비교, 자리바꿈없음 [1, 2, 3, 9]

func bubbleSort(unSortedArray: [Int]) -> [Int] {
    var unSortedArray = unSortedArray
    for index1 in 0..<unSortedArray.count - 1 {
        var swap = false
        for index2 in 0..<unSortedArray.count - 1 - index1 {
            if unSortedArray[index2] > unSortedArray[index2+1] {
                let temp = unSortedArray[index2]
                unSortedArray[index2] = unSortedArray[index2+1]
                unSortedArray[index2+1] = temp
                swap = true
            }
        }
        if swap == false {
            break
        }
    }
    return unSortedArray
}

첫번째 for문은 맨 앞부터 맨 끝까지 2개씩 비교하는 과정의 총 진행할 사이클 횟수이며, '정렬하고자 하는 배열의 인덱스 수 - 1'만큼 진행된다.

두번째 for문은 맨 앞부터 맨 끝까지 2개씩 비교 로직이며, 마찬가지로 원래 '정렬하고자 하는 배열의 인덱스 수 - 1'만큼 진행된다.

하지만 비교 로직을 1번씩 적용할 때 마다, 맨 뒤에서부터 사이클횟수만큼(index1) 이미 정렬되어, 굳이 비교 로직을 진행할 필요가 없기에 사이클횟수(index1)를 빼주며 비교로직을 돌린다.

 

또한, swap이라는 bool 플래그를 통해 2개씩 비교하는 두번째 for문에서 swap이 한번이라도 이루어 지지 않으면, 이미 모두 정렬이 되어있는 상태기 떄문에, 모든 과정을 break 시킨다.