정렬 알고리즘 - 삽입, 버블, 선택

기튼당·2020년 7월 14일

버블정렬 삽입정렬 선택정렬 알고리즘

정렬 알고리즘을 이해하자.
정렬 알고리즘을 JAVASCRIPT로 구현
정렬 알고리즘의 시간복잡도

정렬 알고리즘

일정한 순서대로 정렬하는 알고리즘

삽입 정렬

삽입정렬은 이전수들이 자신보다 크면 해당자리에 삽입되는 정렬방법이다.

예시를보자.

[6, 3, 5, 2, 4, 1, 7] 배열이 주어졌다
2번째 수인 3부터 비교를 시작한다.
이전수인 6이 3보다 크기때문에 3은 6의자리로 삽입되고, 6은 3이있던 자리로 밀려난다.
결과: [3, 6, 5, 2, 4, 1, 7]
그 다음 3번째 수인 5는 이전수인 3과 6하고 비교.
3보다는 크고 6보다는 작기때문에 6의 자리로 이동.
6은 다시 5가있던자리로 밀려난다.
결과: [3, 5, 6, 2, 4, 1, 7]
반복

이제 자바스크립트로 구현해보자.

const arr = [6, 3, 5, 2, 4, 1, 7]; //정렬하기 전 배열

//삽입정렬
function insertsort(arr) {
  let i = 1,
    j,
    temp;
  //배열의 2번째 수부터 비교시작
  for (i = 1; i < arr.length; i++) {
    temp = arr[i];
    //선택된 수보다 이전 숫자들과 비교.
    for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = temp;
  }
  return arr;
}

insertsort(arr); //[1,2,3,4,5,6,7]

버블 정렬

버블정렬은 자신과 바로 다음수와 비교하여 다음수가 값이 더 작다면 자리를 바꾸는 정렬방법

예시를보자.

[6, 3, 5, 2, 4, 1, 7] 배열이 주어졌다
첫번째 수인 6과 다음수인 3을 비교한다.
6이 3보다 크기 때문에 자리를 바꾼다.
결과: [3, 6, 5, 2, 4, 1, 7]
그 다음 6과 5를 비교해준다.
6이 5보다 크기 때문에 자리를 바꾼다.
결과: [3, 5, 6, 2, 4, 1, 7]
반복

이제 자바스크립트로 구현해보자.

const arr = [6, 3, 5, 2, 4, 1, 7]; //정렬하기 전 배열

//버블정렬
function bubbleSort(arr) {
  let temp;
  for (let i = 0; i < arr.length; i++) {
    //앞뒤비교, arr.length -1 -i를 해준 이유는 정렬이후 마지막수는 최대값이 되기때문에 비교를 해줄필요가 없다.
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

bubbleSort(arr); //[1,2,3,4,5,6,7]

선택 정렬

선택정렬은 가장 작은수를 찾아서 맨앞으로 옮겨주는 정렬 방법이다.

예시를보자.

[6, 3, 5, 2, 4, 1, 7] 배열이 주어졌다.
첫번째 수인 6을 기준으로 잡고 그다음 숫자들중 가장 작은숫자를 찾는다.
1이 가장 작은 숫자이기 때문에 1을 가장앞으로 보내고, 6이 그자리로 들어간다.
결과: [1, 3, 5, 2, 4, 6, 7]
그 다음 2번째 수인 3을 기준으로 잡고 동일한 방법으로 가장 작은숫자를 찾는다.
2가 가장 작은 숫자이기 때문에 2가 두번째자리로 가고, 3이 2가 있던 자리로 간다.
결과: [1, 2, 5, 3, 4, 6, 7]
반복

이제 자바스크립트로 구현해보자.

const arr = [6, 3, 5, 2, 4, 1, 7]; //정렬하기 전 배열

//선택정렬
function selectSort(arr) {
  let i, j, temp, minIndex;

  for (i = 0; i < arr.length - 1; i++) {
    minIndex = i;
    for (j = i + 1; j < arr.length; j++) {
      //최소값 index찾기
      if (arr[minIndex] > arr[j]) minIndex = j;
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }

  return arr;
}

selectSort(arr); //[1,2,3,4,5,6,7]