정렬 알고리즘
데이터를 정렬하는 가장 큰 이유는?
-> 탐색(: 데이터의 조회)을 하기 위한 가장 강력한 알고리즘을 사용하기 위해서(이진탐색 알고리즘)
선택정렬
가장 작은것을 가장 앞으로
아래의 이미지는 https://visualgo.net/ko/sorting 에서 플래시로 확인 가능합니다.
위의 경우 3과 비교하다 2가 나왔을때 서로의 위치를 맞바꿔준다.
구현
function selectedSort(arr){
for(let i = 0; i < arr.length; i++){
let minIdx = i;
for(let j = i+1; j < arr.length; j++){
// (첫번째 자리값을 가장 작다고 가정 후 비교)
// 배열의 첫자리값과 i+1값과의 비교후 minIdx 값보다 작다면 minIdx값을 j로 변경
if(arr[minIdx] > arr[j]){
minIdx = j
}
}
// 검사가 끝난 후 minIdx값과 순차적인 인덱스값이 다를경우 스왑
if(minIdx !== i){
let swap = arr[minIdx]
arr[minIdx] = arr[i]
arr[i] = swap
}
}
return arr;
}
selectedSort([1,10,5,8,7,6,4,3,2,9]);
// 결과값
[1,2,3,4,5,6,7,8,9,10]시간복잡도
10 부터 1까지 더한 값(등차수열) : N * (N + 1) / 2 번 가량의 연산을 수행
컴퓨터에서는 가장 큰 차수인 N^2만 보고 O(N^2)이라고 표현하곤 합니다.
(=> N의 값이 커지게 되면, 나누거나 더하는 연산은 의미가 없기 때문에)
버블정렬
옆에 있는 값과 비교하여 작은 값을 앞으로
"bubble up" (한번 반복하게 되면 가장 큰 값이 맨 뒤로)
47, 26이 짝이 됬을 경우 47이 앞으로 바꿔준다.
구현
function bubbleSort(arr){
for(let i = 0; i < arr.length; i++){
for(let j = 0; j < arr.length; j++){
if(arr[j] > arr[j+1]){
let swap = arr[j]
// arr[j]값을 j+1이 아니라 j+i로 바꿔줘서 한참 헤맸다ㅠㅠ
arr[j] = arr[j+1]
arr[j+1] = swap
}
}
// swap 변수와 break문을 활용해서 i의 반복수를 줄일 수 있다.
}
return arr;
}
bubbleSort([1,10,5,8,7,6,4,3,2,9]);위와 같이 작성했지만, 정렬이 제대로 이루어 지지 않았다.
let bubbleSort = (arr) => {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (arr[j] > arr[j + 1]) {
let swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
}
}
}
return arr;
};시간복잡도
O(N^2)
거의 정렬된 상태의 경우 버블정렬은 매우 효과적이다. (정렬의 여부를 확인하는 테스트 용으로 적합)
삽입정렬
필요할때만 위치를 바꾸기(정렬되있다고 가정)
버블정렬과 반대로 가장 작은 값을 앞으로
구현
function insertSort(arr){
for(let i=0; i< arr.length; i++){
let j = i;
while(j >=0 && arr[j] > arr[j+1]){
let swap = arr[j];
arr[j] = arr[j+1];
arr[j+1] = swap
j--;
}
}
return arr
}
시간복잡도
O(N^2)
버블정렬과 마찬가지로 거의 정렬된 상태의 경우 삽입정렬은 매우 효과적이다. (정렬의 여부를 확인하는 테스트 용으로 적합)
퀵정렬
특정 숫자기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다.
*피벗 : 기준 값
구현
시간복잡도
분할정복 알고리즘 -> O(N*logN)
Reference
함께 성장하는 개발자가 되고 싶습니다.