버블 정렬(Bubble Sort)

버블 정렬은 인접한 두개의 요소를 탐색한뒤 정렬하는 방식이다.
단점 : 버블 정렬은 O(n2)의 시간복잡도로 상당히 느린편이다.
장점 : 코드가 간단하다.

버블 정렬은 한번의 순회가 끝날때마다 비교 요소가 줄어든다.
이유는 한번의 순회에서 배열중 가장큰 요소는 마지막 index로 가기 때문이다.
배열의 요소의 count가 n개 라고 가정 하였을 경우
총 n-1번의 순회로 모든 순회는 끝이난다.
배열안 요소가 10개인 경우
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
총 45 순회 하게 된다.

그럼 코드로 살펴보기.

var numbers = [2,6,7,19,11,45,99,56,78,9]

10개의 요소를 가지고있는 배열이다.

for i in 0..<numbers.count {
    for j in 0..<numbers.count {
        if(numbers[i] < numbers[j]) {
            // swap the numbers
           	let temp = numbers[i]
            numbers[i] = numbers[j]
            numbers[j] = temp
        }
        
    }
}

코드 구현..
아주 간단한 코드 이다. 중첩 for문 과 if 문으로 구성되어 있으며
코드를 리뷰해보아도 쉽게 이해간다.
또한

if(numbers[i] > numbers[j]) //내림차순
if(numbers[i] < numbers[j]) //오름차순

이런식으로 조건문만 변경으로 쉽게 차순을 변경할수 있다.

Selection Sort

Selection Sort 는 배열의 첫번째 요소를 가르킵니다.
그 뒤 첫번째 요소의 뒤로 있는 index중 가장 최소의 값을 찾아 둘이 index를 교환합니다.
다음 두번째 요소를 가르키고 첫번째 요소와 같은 방식으로 요소들의 index를 교환합니다.

var numbers = [2,6,7,19,11,45,99,23,56,78,9]

var minIndex = 0

for i in 0..<numbers.count {
    minIndex = i
    for j in (i+1)..<numbers.count {
        if(numbers[j] < numbers[minIndex]) {
            minIndex = j
        }
        numbers.swapAt(i, minIndex)
        
        // swap the values
        //let temp = numbers[i]
        //numbers[i] = numbers[minIndex]
        //numbers[minIndex] = temp
    }
}

배열의 내장함수인 swapAt 으로 쉽게 sort를 실행할수 있습니다.
또한 Selection Sort 와 Bubble Sort 는 중첩 for문안에 조금의 차이가 있습니다.
i + 1 인데요 이것은 배열의 다음 index를 가르키기 위함입니다.

Insertion Sort

Insertion Sort 은 모든 요소들을 이미 정렬된 요소 들과 비교하여 정렬하는 알고리즘 입니다.
조금 다른점은 두번째 index부터 시작되게 됩니다.
그렇게되면 index1 = 정렬시작 index0 = 정렬된 요소 가 될수 있을것 같습니다.
그리고 여기서 key에 선택한 index를 저장하게 됩니다.
이후 key와 내가 전에 선택하여 정렬되어있는 요소들을 비교합니다
마지막으로 정렬이 끝나게되면 내가 선택한 요소 index의 다음을 가르키고 반복되게 됩니다.

var numbers = [2,6,7,19,11,45,99,23,56,78,9]

var minIndex = 0

for i in 0..<numbers.count {
    minIndex = i
    for j in (i+1)..<numbers.count {
        if(numbers[j] < numbers[minIndex]) {
            minIndex = j
        }
        numbers.swapAt(i, minIndex)
    }
}