자바스크립트로 구현하는 기본 정렬들 - 버블 정렬, 선택 정렬

패스트캠퍼스 코딩테스트 강좌의 잔재미코딩 님 부분을 참고하였습니다.

기본 정렬

아래 기본 정렬들의 시간복잡도는 O(n2).

참고 사이트: https://visualgo.net/en/sorting

01. 선택 정렬

주어진 데이터 중 맨 앞 요소와 나머지 요소들을 비교하여 맨 앞 요소가 더 크면 자리를 바꾼다.

위 과정을 마지막 요소를 제외한 모든 요소가 반복한다.

구현

const basicSort = array => {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] > array[j]) {
        [array[i], array[j]] = [array[j], array[i]];
      }
    }
  }
  return array;
};

const array = [23, 456, 123, 567, 34, 13, 67, 2345];
console.log(basicSort(array));

02. 버블정렬

두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬.

예시: https://visualgo.net/en/sorting

구현

const bubblesort = data => {
  // 크기 비교를 전체 데이터 길이 -1만큼 반복
  for (let i = 0; i < data.length - 1; i++) {
    let swap = false; // 변화가 있는지 없는지 확인
    for (let j = 0; j < data.length - i - 1; j++) {
      // 앞 데이터가 뒤 데이터보다 크다면
      if (data[j] > data[j + 1]) {
        // 스와핑
        [data[j], data[j + 1]] = [data[j + 1], data[j]];
        swap = true;
      }
    }
    // 비교했는데 변화가 없다는 것은 이미 정렬이 완료된 것이므로 종료
    if (!swap) {
      break;
    }
  }
  return data;
}

const array = [12, 44, 56, 34, 87, 32, 75, 1, 3, 6, 2];

console.log(bubblesort(array));