컴퓨터를 공부하고자 마음먹은지 N일차

[104일차]각종 정렬알고리즘 -삽입, 선택, 거품 본문

🎲Algorithm

[104일차]각종 정렬알고리즘 -삽입, 선택, 거품

졸린새 2020. 12. 22. 03:48
728x90

거품정렬

거품정렬은 원소이름이 거품이 수면위로 올라오는것 처럼 정렬이 되어가기 때문에
붙여진 이름이다.
거품정렬을 이해하는데에는 이만한 춤영상 이 없다.

javascript 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  // 배열이 정렬이 덜됐는지 확인해주는 boolean타입값을 true로 선언한다.
  // 순서대로 정렬되어 있을 때 까지 반복한다 boolean이 true일때
    //boolean값을 false로 설정한다.
    //배열의 길이만큼 반복한다
      //i번째 인덱스가 i + 1 번째 인덱스보다 크면
      //자리를 바꾼다
      //boolean값을 true로 설정한다.
  // 정렬된 배열을 리턴한다.
 
  let notYet = true;
 
  while(notYet){
    notYet = false;
    for(let i = 0; i < arr.length; i++){
      if(arr[i] > arr[i + 1]){
        let swap = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1= swap;
        notYet = true;
      }
    }
  }
  return arr;
};
cs

시간복잡도
O(n^2)
___

삽입정렬

앞에서 부터 차례대로 바꿀값의 위치를 찾아서 넣어들어가는 알고리즘
출처 - “Visualising Sorting Algorithms”
출처 - “Visualising Sorting Algorithms"

javascript코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function insertionSort(arr){
  // 1번째 인덱스부터 순회한다.
    //바꿀값을 i인덱스값으로 설정한다.
    //j는 i - 1 부터 시작한다 바꿀값이 j번째 인덱스값보다 작을 때 까지 순회한다.
    //j는 1씩 줄어든다.
      //j인덱스 값을 오른쪽으로 밀어낸다(j+1번째 인덱스값에 j번째 인덱스값을 할당한다.)
    //j + 1번째 인덱스 값에 i번째 인덱스값을 할당한다.
  let i, j;
  for(i = 1; i < arr.length; i++){
    let key = arr[i];
    for(j = i - 1; j >= 0 && key < arr[j]; j--){
      arr[j + 1= arr[j];
    }
    arr[j + 1= key;
  }
  return arr;
}
cs

시간복잡도
O(n^2)

선택정렬

배열 중 가장 작은값을 찾고 그 값을 맨앞에 위치한 값과 바꾼다.
이걸 배열의 길이만큼 반복한다.
이미지
출처-위키피디아

javascript코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function selectionSort (arr){
  //초기값 i를 설정한다 시작값0 (배열순회)
    //최솟값을 설정한다 기본값은 i
    //초기값 j를 설정한다 시작값은 i + 1(i + 1부터 배열순회)
      //arr[min]이 arr[j]보다 크면 
        //최소값은 j가된다.
    //최소값과 i값을 바꿔준다.
  for(let i = 0; i < arr.length; i++){
    let min = i;
    for(let j = i + 1; j < arr.length; j++){
      if(arr[min] > arr[j]){
        min = j;
      }
    }
    let dummy = arr[min];
    arr[min] = arr[i];
    arr[i] = dummy;
  }
  //정렬된 배열을 리턴한다.
  return arr;
}
 
cs

시간복잡도
O(n^2)

정렬알고리즘 중 복잡도가 n^2 인 알고리즘 위주로 알아봤다.
다음시간엔 병합정렬 그리고 퀵정렬에 대해서 알아보자.
각각 따로 포스팅 할듯.

Comments