① 두 인접한 데이터를 비교한다
② 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 둘의 자리를 바꿔준다
이렇게 한번으로 정렬 안되면 전체 정렬이 될 때까지 반복한다.
1-1.
인접 데이터끼리 비교하며 swap하는 작업 (스캔 작업)은 총 (탐색하는 요소의 갯수 - 1) 만큼 진행하면된다.
2-1.
한번의 스캔은 끝났지만 전체 정렬까지 반복해야하는데,
스캔 작업을 한 번 할 때마다 큰 값부터 하나씩 정렬될 테니, 스캔 작업을 최대 (배열 요소의 갯수 - 1) 만큼 진행하면 전체 배열이 정렬되는 것이다.
10개 중 9개 정렬하면 제일작은 값 하나는 자동으로 0 인덱스에 들어있게 될 것이니 count - 1 을 하면 된다.
func bubbleSort(_ array: inout [Int]) {
for index1 in 0..<(array.count - 1) { // 스캔 작업 반복
var isSwap = false
for index2 in 0..<((array.count - index1) - 1) { // 스캔 작업(인접 인덱스 비교 및 swap 반복) : (탐색하려는 요소의 갯수) - 1 => 탐색하려는 요소의 갯수는 스캔 횟수에 따라 차감됨(스캔 횟수만큼 정렬되어 있을테니)
if array[index2] > array[index2 + 1] {
array.swapAt(index2, (index2 + 1))
isSwap = true
}
}
if isSwap == false { return }
}
}
여기서 isSwap은??
만약 스캔할 때 swap이 전혀 일어나지 않으면 이전 index값이 다음것보다 클 수가 없다는 의미로 모두 정렬이 되었다는 뜻이니 리턴으로 끝내버리면 된다.
① 데이터 중 가장 작은 값을 찾는다
② 찾은 값을 데이터 맨 앞 값과 교체한다
③ 맨 앞 데이터를 제외하고 위 과정을 반복한다
이렇게 0번 index부터 가장 작은 값으로 채워나가는 정렬 방법이다.
func selectionSort(_ array: inout [Int]) {
for stand in 0..<(array.count - 1) { // 스캔 작업 반복
var minIndex = stand
for index in (stand + 1)..<array.count { // 스캔 작업 (stand가 0이면 1번 index부터 마지막 Index까지 돌며 최소값을 찾아야 하니까)
if array[index] < array[minIndex] {
minIndex = index
}
}
array.swapAt(stand, minIndex)
}
}
① 정렬은 두 번째 요소부터 시작한다
② 기준이 되는 index와 인접한 index부터 비교하며 삽입한다
③ 삽입이 끝나면, 기준 index의 다음 index를 기준으로 잡는다
=>
기준 index는 1부터 시작하며, 기준 index에 인접한 이전 index부터,
기준 index의 값보다 작은 놈을 만날 때까지 swap하다가, 작은놈을 만나면 종료
한 번 스캔이 끝나면, 기준 index의 다음 index를 기준으로 잡고 다시 스캔 진행
func insertionSort(_ array: inout [Int]) {
for stand in 1..<array.count {
for index in stride(from: stand, to: 0, by: -1) {
if array[index] < array[index - 1] {
array.swapAt(index, index - 1)
} else {
break
}
}
}
}
stride 메서드는 to 이전까지만 반복이 된다고 한다!
https://babbab2.tistory.com/97?category=908012
https://babbab2.tistory.com/98?category=908012