22-11-01-자료구조, 알고리즘 (2)

정렬

선택정렬

주어진 리스트 중에서 최솟값을 찾는다.
그 리스트의 최솟값을 맨 앞 값의 위치와 교체한다.
맨 앞을 제외한 나머지 리스트들을 계속해서 정렬한다.

• 다른 빈 배열에 최솟값을 차례대로 넣는 리스트로 구현하기

let 입력값 = [199, 22, 33, 12, 32, 64, 72, 222, 233];
let 정렬된배열 = [];

function selectionSort(arr) {
	for (let i = 0; i < 입력값.length; i++) {
    	let min_index = i;
      	for (let j = i + 1; j < arr.length; j++) {
        	if (arr[min_index] > arr[j]) {
            	min_index = j;
            }
        }
      	let temp = arr[min_index];
      	arr[min_index] = arr[i];
      	arr[i] = temp;
    }
  	return arr;
}
console.log(selectionSort(입력값));

삽입정렬

두 번째 인덱스부터 시작하여 그 앞의 원소들을 비교하면서 자신이 들어갈 위치를 지정한 후 그 뒤의 원소들의 위치를 옮긴 후 그 자리에 삽입하여 정렬하는 알고리즘
-> 비용이 많이 든다. (하나씩 모두 이동해야 함)

• 첫번째 수를 따로 배열에 넣은 후 그 다음 수부터 앞 / 뒤 위치 결정하여 넣는 리스트 구현하기

let 입력값 = [199, 22, 33, 12, 32, 64, 72, 222, 233];
let 정렬된배열 = [];
let 배열의길이 = 입력값.length;

function 삽입값이_들어갈_인덱스(정렬된배열, 삽입값) {
    for (const i in 정렬된배열) {
        if (삽입값 < 정렬된배열[i]) {
            return i;
        }
    }
    return 정렬된배열.length;
}

for (let i = 0; i < 배열의길이; i++) {
    let 삽입값 = 입력값.shift();
    let 인덱스 = 삽입값이_들어갈_인덱스(정렬된배열, 삽입값);
    정렬된배열.splice(인덱스, 0, 삽입값);
}

console.log(정렬된배열);

병합정렬

분할 정복
하나로 남을 때까지 반으로 쪼갠 후 서로 정렬하면서 결합한다.

let 입력값 = [5, 10, 66, 77, 54, 32, 11, 15];

function 병합정렬(입력배열)) {
	// 분할하기
  let 입력배열길이 = 입력배열.length;
  let 결과값 = [];
  if (입력배열길이 <= 1) {
  	return 입력배열;
  }
  let 중간값 = parseInt(입력배열의길이 / 2);
  let 그룹1 = 병합정렬(입력배열.slice(0, 중간값));
  let 그룹2 = 병합정렬(입력배열.slice(중간값));
  
  // 정복
  while(그룹1.length != 0 && 그룹2.length != 0) {
  	if (그룹1[0] < 그룹2[0]) {
    	결과값.push(그룹1.shift());
    } else {
    	결과값.push(그룹2.shift());
    }
  }
  결과값 = [...결과값, ...그룹1];
  결과값 = [...결과값, ...그룹2];
  return 결과값;
}
console.log(병합정렬(입력값));

퀵 정렬

• 피봇값을 기준으로 정렬 (처음값, 중간값, 마지막 값)
• 기준으로 앞 뒤에 값들 넣음

let 입력값 = [66, 77, 54, 32, 10, 5, 11, 15]
function 퀵정렬(입력배열) {
	let 입력배열길이 = 입력배열.length;
  	if (입력배열길이 <=1) {
    	return 입력배열;
    }
  	let 피벗값 = 입력배열.shift();
  	let 그룹1 = [];
  	let 그룹2 = [];
  
  	for (let i in 입력배열) {
    	if( 입력배열[i] < 피벗값) {
        	그룹1.push = 입력배열[i];
        } else {
        	그룹2.push = 입력배열[i];
        }
    }
  	console.log();
  	return 퀵정렬(그룹1).concat(피벗값, 퀵정렬(그룹둘));
}
퀵정렬(입력값);