최소값 구하기(Math.min(), 정렬 알고리즘)

나는 최소값을 구하기 위해서 인덱스 0번째를 최소값으로 잡고

다른 인덱스와 비교하는 방법을 사용하였다.

let arr = [4,1,5,3]
let min = arr[0]//일단 인덱스 0번째로 잡아서 비교하는 방법
for(let i = 1; i<arr.length; i++){
	if(arr[i] < min)
    	min = arr[i]
}

 

두번째 방법으로는 배열을 sort()함수를 사용해 오름차순으로 정렬한뒤에 0번째 index를 뽑는 방법도 있을 것이다.

 

다른 사람들의 코드를 보니 다양한 방법이 있어서 정리해보았다.

Math.min()

Math.min(...arr)

arr.reduce((a,b) => Math.min(a,b))

Math.max를 사용하면 최댓값도 구할 수 있어서 유용한 방법이다.

 

정렬 알고리즘을 공부중인데 이 방법들을 사용해도 최소값을 구할수 있을 것같아 정리해보았다.

 

선택정렬

가장 직관적이고 원시적인 방법으로 가장 작은것을 찾아 제일 앞으로 보낸다.

즉 전체 index중 제일 작은것을 0번째 index로 보내고

그다음에 1번째 index부터 끝까지 제일 작은 것을 찾을경우 1번째 index와 교체한다.

그다음에 2번째 index부터 끝까지 제일 작은 것을 찾을경우 2번째 index와 교체한다.

이를 반복한다..

let temp;
let min;
let index;
for(let i = 0; i<arr.length; i++){
    min=10//임의의 제일큰수
    for(let j = i; j<arr.length; j++){
        if(min > arr[j]){
            min = arr[j]
            index = j
        }
    }
    //가장작은 값을 i번째 인덱스와 스와핑(교체한다)
        temp = arr[i]
        arr[i] = arr[index]
        arr[index] = temp;
}
arr.forEach(e => console.log(e))

 

버블정렬

버블정렬도 직관적으로 옆에있는 값을 비교해서 작은값을 앞으로 보내주는것을 반복한다.

한번 돌았을때 가장 끝에는 큰값이 올 수있다.

그다음에 인덱스 0번부터 인덱스 마지막-1번까지 버블정렬을 한다.

그 다음에 인덱스 0번부터 인덱스 마지막-2번까지 버블정렬을 한다.

반복한다...

구현은 가장쉽지만 가장 비효율적이라고한다.

let temp
for(let i = 0; i<arr.length; i++){
    for(let j = 0; i<arr.length-i; j++){
        if(arr[j] > arr[j+1]){
            temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp
        }
    }
}
console.log(arr)

 

삽입정렬

각 숫자를 적절한 위치에 삽입하는 방법. 무조건 위치를 바꾸는 것이 아니라 필요할때만 위치를 변경하는 것이 특징이다. 이때문에 선택정렬과 버블정렬보다 빠르다고한다.

먼저 1번째 index를 앞의 index와 비교하여 정렬할 값이 있을 경우에만 적당한 위치로 이동시켜준다.

이제 2번째 index와 앞의 index들을 비교하여 정렬할 값이 있을 경우에만 적당한 위치로 이동시켜준다.

이 과정을 반복한다.. 참고로 이미 앞의 index들은 정렬이되어있기때문에 연산속도가 비교적 빠르다.

let j;
for(let i = 0; i<arr.length; i++){
    j = i
    while(arr[j] > arr[j+i]){
        temp = arr[j]
        arr[j] = arr[j+i]
        arr[j+i] = temp
        j--
    }
}

 

선택정렬, 버블정렬, 삽입정렬 모두 시간복잡도는

O(N^2)번이라하고 상황에 따라 비효율적이라고한다.