[알고리즘] 정렬

옒·2022년 3월 21일

자료구조 & 알고리즘

목록 보기

7/9

우선 정렬 알고리즘 종류에는 Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, Shell Sort, Merge Sort, Heap Sort, Radix Sort등이 있다.

실행 방법에 따른 분류

비교식 정렬(comparative sort)와 분산식 정렬(distribute sort)가 있다.

비교식 정렬 비교하고자 하는 각 키값들을 한 번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법
분산식 정렬 키값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법이다.

정렬 장소에 따른 분류

내부 정렬(internal sort)와 외부 정렬(external sort)가 있다.

내부 정렬
- 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식이고 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라서 제한된다.
- 교환 방식(Selection, Bubble, Quick), 삽입 방식(Insertion, Shell), 병합 방식(2-way 병합, n-way 병합), 분배 방식(Radix), 선택 방식(Heap, Tree) 등이 있다.
외부 정렬
- 정렬할 자료를 보조 기억장치에서 정렬하는 방식이고 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬이 가능하다.
- 병합 방식(2-way 병합, n-way 병합) 이 있다.

정렬 알고리즘 기초

버블 정렬

인접한 두 개의 원소를 비교하여 자리를 교환하는 방식

예시) 오름차순

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

ZeroCho Blog

퀵소트

분할 정복을 사용하는 정렬 방법

예시) 오름차순

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]