우선 정렬 알고리즘 종류에는 Selection Sort
, Bubble Sort
, Quick Sort
, Insertion Sort
, Shell Sort
, Merge Sort
, Heap Sort
, Radix Sort
등이 있다.
비교식 정렬(comparative sort)와 분산식 정렬(distribute sort)가 있다.
내부 정렬(internal sort)와 외부 정렬(external sort)가 있다.
인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
예시) 오름차순
var bubbleSort = function(array) {
var length = array.length;
var i, j, temp;
for (i = 0; i < length - 1; i++) { // 순차적으로 비교하기 위한 반복문
for (j = 0; j < length - 1 - i; j++) { // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문
if (array[j] > array[j + 1]) { // 두 수를 비교하여 앞 수가 뒷 수보다 크면
temp = array[j]; // 두 수를 서로 바꿔준다
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
};
bubbleSort([5,1,7,4,6,3,2,8]);
코딩테스트, 초급, 버블정렬,Bubble Sorting
분할 정복을 사용하는 정렬 방법
예시) 오름차순
const quickSort = function (arr) {
if (arr.length <= 1) return arr; //나누고 나누다 배열이 1개가 되면 정렬할 필요 없으니 리턴
const pivot = arr[0]; //피봇을 가장 첫번째 걸로...굳이? => start, end포인터를 안써서 그런가?
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) { //배열 순회
if (arr[i] <= pivot) left.push(arr[i]); //현재 인덱스의 값이 피봇보다 작거나 같다면 왼쪽(작은 것들)이 될 배열에 푸시
else right.push(arr[i]);//피봇보다 크다면 오른쪽(큰 것들)이 될 배열에 푸시
}
const lSorted = quickSort(left);//나눠진 왼쪽 배열에서 다시 퀵소트
const rSorted = quickSort(right);//나눠진 오른쪽 배열에서 다시 퀵소트
return [...lSorted, pivot, ...rSorted];//정렬된 값들을 합쳐서 리턴
};
출처: https://im-developer.tistory.com/135 [Code Playground]
코딩테스트, 기초, 퀵정렬, 퀵소트, Quick Sort
[CS]Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
JavaScript로 퀵정렬(quick sort)알고리즘 구현하기