목록정렬알고리즘 (2)

Run with coding

누구나 자료 구조와 알고리즘 | 긍정적인 시나리오 최적화 | 삽입 정렬 알고리즘

✔️ 삽입 정렬 1. 인덱스 1의 값을 변수에 담아둔다. 2. 왼쪽의 값과 변수에 담아둔 값을 비교한다. 3. 왼쪽 값이 더 크다면 오른쪽으로 쉬프트, 작다면 해당 패스스루 끝내기 4. 쉬프트하여 빈 자리에 변수로 담아둔 값을 넣는다. 5. 마지막 인덱스까지 반복 ✔️ 삽입 정렬 코드 구현 ✔️ 삽입 정렬의 효율성 원소가 N개인 배열 비교 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교 시프트 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교 삭제 : N-1번 삽입 : N-1번 총 단계 수 : N^2 + 2N - 2단계 원소가 5개인 배열 비교 : 1 + 2 + 3 + 4 = 10번 시프트 : 1 + 2 + 3 + 4 = 10번 삭제 : 4번 삽입 ..
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 14. 14:45
누구나 자료 구조와 알고리즘 | 빅 오를 사용하거나 사용하지 않는 코드 최적화 | 선택 정렬

✔️선택 정렬 선택 정렬 방법 앞에서부터 순서대로 돌면서 최솟값이 있는 인덱스를 변수에 저장 다 돌았을 때 시작 인덱스와 변수에 저장된 인덱스의 값을 바꾼다. 배열 끝에서 시작하는 패스스루에 도달할 때까지 계속 반복 선택 정렬 실제로 해보기 선택 정렬의 효율성 버블 정렬의 단계 수 / 2 = 선택 정렬의 단계 수 즉, 선택 정렬의 단계 수는 O(N^2) / 2이다. 상수 무시하기 O(N^2 / 2) 이지만 빅오 표기법은 상수를 무시한다. 즉, /2를 버리고 O(N^2)로 표기한다. 그래서 버블 정렬과 선택 정렬의 실제 성능 차이는 크지만 빅 오 표기법만 봤을 땐 둘의 단계 수가 같다. 👉🏻 빅오만 보고 성능을 판단하기 쉽지 않다는 뜻이다. 빅 오의 또 다른 개념 빅 오 표기법은 일반적인 카테고리의 알고리..
코딩테스트 | 자료구조 | 알고리즘 2023. 5. 20. 09:00
이전 Prev 1 Next 다음