TIL#10(정렬, 정수 내림차순 정렬)

오늘 한일

• 정렬

1. bubble sort(버블 정렬) - 구현이 쉽지만 시간이 오래 걸려 비효율적이다.

버블 정렬 코드

버블정렬 시간복잡도

2. insertion sort(삽입 정렬) - 최선의 경우 O(N)으로 경굉히 빠르지만 최악의 경우 O(N^2)으로 데이터 상태에 따라서 성능 차이가 심하다.

삽입 정렬 코드

삽입정렬 시간복잡도

3. selection sort(선택 정렬) - 구현이 쉽고 비교하는 횟수에 비해 교환이 적게 일어나지만 시간이 오래 걸려 비효율적이다.

선택 정렬 코드

선택 정렬 시간복잡도

• 정수 내림차순으로 배치하기(프로그래머스)

문제 풀이

어려웠던 점

• 정렬의 시간복잡도에 대한 개념을 잘 몰라 시간 복잡도를 보고 이 알고리즘이 어느 정도의 성능을 보여주는지 알기 어려웠다. (시간복잡도와 Big-O표기법에 대해 알아보았다.)
• paresInt 나 Array.form, toString, sort, reverse, join등 문제 풀이에 필요한 메서드를 바로바로 떠올려서 조합하기 어려웠다. (JS를 더 많이 다뤄보면 익숙해 질 것 이다.)

오늘의 TIP

• 시간복잡도의 빠르기

O(1)이 빠른쪽이고 O(2^n)이 느린쪽이다