컴퓨터를 공부하고자 마음먹은지 N일차
[104일차]각종 정렬알고리즘 -삽입, 선택, 거품 본문
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"
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 인 알고리즘 위주로 알아봤다.
다음시간엔 병합정렬 그리고 퀵정렬에 대해서 알아보자.
각각 따로 포스팅 할듯.
'🎲Algorithm' 카테고리의 다른 글
[115일차]동적 프로그래밍 (0) | 2021.01.02 |
---|---|
[111일차]퀵정렬 알고리즘(Quick sort) (1) | 2020.12.29 |
[110일차]병합정렬 알고리즘(merge-sort) (1) | 2020.12.28 |
[107일차]이진탐색 알고리즘 (2) | 2020.12.24 |
[99일차]그래프 너비우선탐색법 (BFS) (0) | 2020.12.18 |
Comments