728x90
반응형
문제
BubbleSort를 .sort 메소드를 쓰지말고 직접 구현해보는 문제.

배울점
1. bubbleSort 자체가 두 값을 비교하여 큰 값을 뒤로 보내는 방식이다.
2. bubbleSort가 1회 실행되면, 리스트에서 가장 큰 값은 리스트의 제일 뒤쪽으로 가게 되며 이것은 1개의 값이 정렬된 것이라고 볼 수 있다.
ex) [3, 4, 5, 9, 1, 2]와 같이 제일 큰 수 9가 애매한 위치에 있더라도 두 값의 위치를 바꾸는 것을 순차적으로 진행하면 9가 리스트의 맨 끝에 오게됨을 알 수 있다.
3. 최적화를 위해 6번줄에서와 같이 len - 1 - i를 반복문의 범위로 준다. 즉, 맨 뒤쪽의 정렬된 큰 값들은 신경쓰지 않도록 한다.
4. 2개의 값을 바꾸는 로직은 9번줄과 같이 ES6의 구조분해할당을 써도 되고, 임시변수 tmp를 지정하여 바꿔줘도 된다.
5. count 값을 지정하여 이미 정렬이 되어서 bubbleSort가 진행되지 않으면 반복문을 중단시키도록하여 최적화해준다.
728x90
반응형
'Computer Science > Algorithm' 카테고리의 다른 글
Prm 7 : tree DFS / recursion (0) | 2021.01.04 |
---|---|
Prm 6 : Sudoku / parseInt, [...Array().keys()].slice() (0) | 2021.01.01 |
Prm 3 : Subset (0) | 2020.12.28 |
Prm 2 : fibonacci (0) | 2020.12.27 |
Prm 1 : permutation (0) | 2020.12.25 |