정렬 알고리즘

‘정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?’

정렬을 하고 난 후, 검색을 시작해야 효율성이 극대화 된다.!

버블정렬

매우 기본적인 정렬 알고리즘

1. 배열 내에서 연속된 두 항목을 가리킨다. (1번째 원소, 2번째 원소)

2. 두 항목의 순서가 뒤바뀌어 있으면 두 항목을 교환한다. (순서가 올바르다면 아무것도 하지않는다.) (*여기서 순서란 오름차순 -> 큰게 앞에 있으면 교환)

3. 포인터를 오른쪽 한 셀씩 옮긴다.

4. 배열의 끝까지 또는 이미 정렬된 값까지 1단계부터 3단계를 반복한다. (패스쓰루 - 첫패스쓰루시, 마지막 원소는 가장 값이 높은 값으로 배치된다. 변동 x)

5. 이제 두 포인터를 다시 배열의 처음 두 값으로 옮겨서 1단계부터 4단계를 다시 실행함으로써, 새로운 패스스루를 실행한다. (교환이 일어나지 않는 패스스루가 생길때까지 패스스루를 반복한다. 교환할 항목이 없다는 것은 배열이 정렬됐고 문제를 해결했다는 뜻)

*두번째 패스스루시, 첫번째 패스스루를 통해 이미 올바른 위치로 간 마지막 원소와는 비교할 필요가 없다.

→ 각 패스스루마다 정렬되지 않은 값 중 가장 큰 값, “버블”이 올바른 위치로 가게된다.

패스스루란?
배열의 모든 요소를 한 번 순회하며, 연속된 두 항목을 비교하고 교환하는 단계를 의미한다. 즉, 배열의 처음부터 끝까지 또는 남은 정렬되지 않은 부분까지 한 번의 정렬 과정을 수행하는 것을 "패스스루"라고 한다.

버블정렬 도식화

버블정렬 코드

function bubble_sort(list){
	let unsorted_until_index = list.length -1;
	let sorted = false; // 최적화를 위해
		
	while(!sorted){ // 루프 한 번이 패스스루
		sorted = true;
		for(let i=0; i<unsorted_until_index; i++){
			if(list[i]>list[i+1]){
				let flag = list[i]
				list[i]= list[i+1]
				list[i+1] = flag
				sorted = false;
			}
		}
		unsorted_until_index -=1;
	}
	return list
}

버블정렬의 효율성

비교 : 어느 쪽이 더 큰지 두 수를 비교한다.
교환 : 정렬하기 위해 두 수를 교환한다.

• 비교

원소 N개 일 때, → N-1 + N-2 + N-3 + …. + 1 비교를 한다.

• 교환

배열이 내림차순으로 정렬된 최악의 시나리오라면 비교할 때마다 교환을 해주어야한다.
즉, 10번의 비교가 있으면 10번 교환해주어야한다.

N(비교) * N(교환)

→ 버블정렬에는 값이 N개 일 때, N^2의 단계가 필요하고, 빅오 표기법으론 O(N^2) 이다.

O(N^2)은 상대적으로 느린 알고리즘으로 간주되기 때문에, 시간을 들여 더 빠른 대안은 없을지 깊이 고민해보기!

O(N^2) 을 O(N) 으로!

배열에 중복되는 숫자가 있는지 확인하는 알고리즘

function hasDuplicateValue(array){
	for(let i=0; i<array.length; i++){
		for(let j=0; j<array.length; j++){
			if(i !== j && array[i] === array[j]) return true;
		}
	}
	return false;
}

최악의 시나리오 : 배열이 중복값을 포함하지 않는 경우
이 경우, 코드는 false를 반환하기 전까지 모든 루프를 수행해야하고, 가능한 모든 조합을 전부 비교한다.

결론적으로, 원소 N개가 있을 때 함수는 N^2 번의 비교를 수행한다.

시간복잡도 : O(N^2)

루프 내에 다른 루프를 중첩하는 알고리즘 → O(N^2)

중첩루프를 쓰지않고, 중복되는 숫자 확인 알고리즘 (해시테이블 기반)

function hasDuplicateValue(array){
	let existingNumbers = [];
	for(let i=0; i<array.length; i++){
		if(existingNumbers[array[i]]===1){
		return true;
		}else{
		existingNumbers[array[i]] = 1;
		}
	}
	return false;
}

1. existingNumbers 빈배열 생성
2. array의 숫자들을 확인하면서, 숫자가 나올 때마다 existingNumbers 배열에 그 숫자에 해당하는 인덱스에 임의 값(숫자 1)을 넣는다. → (ex. array: [4,1,3] → [undefined, 1, undefined, 1, 1] ).
3. existingNumbers의 인덱스를 사용해 지금까지 array에서 어떤 숫자들이 나왔었는지 기억할 수 있다.
4. 이제 이 인덱스의 값이 이미 1인지 확인한다. (existingNumbers 배열에 삽입도 단계수로 계산해야하지만, 삽입 유형은 중요하게 보지 않는다.)

데이터 원소가 N개있을 때 비교를 N번한다. 단 하나의 루프에서 단지 배열에 있는 원소 수만큼 순회하기 때문

시간복잡도 : O(N)

(but, 단점: 첫번째 방식보다 메모리를 더 소비한다. ex. 만약 값이 2000이라면? 배열 index로 2000까지 생성된다.)

cf. 우테코 로또문제를 내가 이렇게 풀었다! 로또 45개 배열을 미리 만들어놓고, 당첨 번호들에만 1씩 채워서 매치하는 방식으로 당첨을 조회했다!

마무리

빅오표기법이 유일할까?

아니다!. 빅오표기법이 알고리즘을 서로 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해주는 도구이지만, 실제로 빅오표기법에서는 한 알고리즘이 다른 알고리즘보다 훨씬 빠른 경우에도 두 경쟁 알고리즘을 정확히 똑같은 방식으로 표현하기도 한다.