[이것이 코딩테스트다] 6. 정렬
코딩테스트에서 정렬알고리즘이 사용되는 경우는 일반적으로 3가지 문제유형
- 정렬 라이브러리로 풀 수 있는 문제
- 정렬 알고리즘의 원리에 대해서 물어보는 문제
- 더 빠른 정렬이 필요한 문제
개념
선택정렬 : 가장 작은 수를 선택하여 index[0]과 교환
시간복잡도 O(n*n)
for (let i = 0 ; i < arr.length-1 ; i++) {
let min = Math.min(...arr.slice(i,)) ;
let min_Spot = arr.indexOf(min) ;
let change = arr[i];
arr[i] = min ;
arr[min_Spot] = change ;
}
삽입정렬 : 첫번째 수가 정렬 완료라는 가정하에 수가 앞에서부터 작으면 왼쪽, 크면 오른쪽에 삽입
시간복잡도 O(n*n) // 거의 정렬이 되어있는 상황에서는 효율적
//내가 만든 코드
let arr = [1,5,2,7,4,9,3,8] ;
for(let i = 1 ; i < arr.length ; i++ ) {
for (let j = 0 ; j < i ; j++){
if (arr[i] < arr[j] ){
let k = arr[i] ;
for (let n = i ; n > j ; n--) {
arr[n] = arr[n-1] ;
}
arr[j] = k ;
}
}
}
>> 내가 만든 코드보다 다른사람 코드가 더 빠를 것 같음. 나는 숫자를 앞에서부터 자리를 찾아 그 뒷자리를 미루는 방식으로 구성, 타인은 숫자를 그 바로 앞자리와 비교해서 크면 바꾸는 식으로 해서 확인하는 시간을 줄임.
퀵정렬: [0]을 기준값으로 설정 > 왼쪽부터 기준보다 큰값을, 오른쪽부터 기준보다 작은값을 탐색 > 두 수를 발견 시 교환 >
이를 무한으로 반복 > 만약 모두 교환하여 왼값과 오른값이 교차될 경우 기준값을 가운데로 배치 >
기준값을 기준으로 왼쪽, 오른쪽을 각각 재귀 돌림 > 돌리고자 하는 arr의 길이가 1개일 때 중지
시간복잡도 : 0(N log N) // 이미 정렬이 어느정도 되어있는경우에는 비효율(시간복잡도가 N*N가 될 수 있음)
let arr = [6,5,2,7,4,9,3,8] ;
function qS(arr, a, b){ //초기값 a=0 b=arr.lenght-1
if (a >= b) return
let privot = a, left = a+1, right = b ;
//후에 swap해줘야해서 값 자체로 설정하면 안됨
let val ;
while (left <= right ){ //조건에 어긋난다면 이미 기준값이 가운데로 와있는 상황
while ((left <= b )&&(arr[left]<= arr[privot])) { left++ }
while ((right > a )&&(arr[right] >= arr[privot])) { right-- }
if (left > right) {
//교차되는 경우 기준값을 right와 바꿈, 그래서 아래 재귀함수의 기준점이 right
val = arr[right] ;
arr[right] = arr[privot] ;
arr[privot] = val ;
} else { //아직 교차하기 전이면 더 둘이 교환만하고 추가탐색
val = arr[left] ;
arr[left] = arr[right] ;
arr[right] = val ;
}
}
qS(arr, a, right-1) ; //왼쪽arr 재귀함수
qS(arr, right+1, b) ; //오른쪽arr 재귀함수
}
qS(arr,0,7)
console.log(arr) ;
계수정렬 : index를 이용하여 데이터 갯수를 값으로 설정
특정 조건(데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때)이 부합할때만 사용가능하지만 매우 빠름.
가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적. 앞선 비교 기반의 정렬 알고리즘이 아님.
데이터의 갯수보다 데이터의 크기에 영향을 받음. 1과 99,999,999가 있다면 해당 정렬은 비효율적.
더불어 같은 값이 많다면 효과적.
시간복잡도 O(N+K)
let count = "0".repeat(Math.max(...arr)+1).split("").map(Number) ;
arr.forEach(x=>count[x]++) ;
let result = []
for (let i = 1 ; i < count.length ; i++ ){
if ( count[i] != 0 ) {
for (let j = 1 ; j <= count[i] ; j++) {result.push(i)}
}
}
[예제문제] 위에서 아래로
둘째줄부터 N개의 수가 입력된다. 수의 범위는 1이상 100,000이하의 자연수.
입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다.
첫째줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 ≤ N ≤ 500)
let n = input.shift() ;
console.log(input.sort((a,b) => b- a).join(" ")) ;
[예제문제] 성적이 낮은 순서로 학생 출력하기
N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
let input = require('fs').readFileSync('input.txt').toString().trim().split("\\n") ;
let n = Number(input.shift()) ;
input = input.map(x => x.split(" ")) ;
input.sort((a,b) => a[1] - b[1]) ;
input.forEach(function(x){
console.log(x[0]) ;
})
>> 배열의 index[1]을 기준으로 정렬
[예제문제] 두 배열의 원소 교체
두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기 연산을 수행할 수 있다. N, K, 그리고 배열 A와, B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
let input = require('fs').readFileSync('input.txt').toString().trim().split("\\n") ;
let [n,m] = input.shift().split(" ").map(Number) ; //m=K
let a = input.shift().split(" ").map(Number).sort() ;
let b = input.shift().split(" ").map(Number).sort((a,b)=> b-a) ;
for( let i = 0 ; i < m ; i++) {
**if (a[i] < b[i]) { //(1)**
let j = a[i] ;
a[i] = b[i] ;
b[i] = j ;
}
}
console.log(a.reduce((a,b) => a+b, 0));