[TIL] 내일배움캠프 78일차(23.07.31.) - 선택 정렬

To-do

• 알고리즘 스터디 문제 풀기 및 발표 자료 정리
• 플러스 주차 복습 과제 작성: 게시글 조회 API
• 스프링 심화 개선 과제 작성: Controller 테스트 코드 작성하기

---

TIL

< 선택 정렬 >

• 선택 정렬?

* 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
   1. 주어진 리스트 중에 최소값을 찾는다.
   2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
   3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
* 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 O(n2) 만큼의 시간이 걸린다.
* 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

 

• 거품 정렬과의 비교

시간 복잡도 O( n 2 )인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수하다.

 

• 소스 코드

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

 

• 참조 링크: https://ko.wikipedia.org/wiki/선택_정렬

선택 정렬 - 위키백과, 우리 모두의 백과사전

 

* 정렬 관련 참고 블로그

https://velog.io/@minji0801/버블정렬-vs-선택정렬-vs-삽입정렬-차이-제대로-알고가자#1-bubble-sort버블-정렬

[Algorithm] 버블 정렬 vs 선택 정렬 vs 삽입 정렬 차이 제대로 알고가자.

 

---

Next...

• JPA 강의 듣기
• 플러스 주차 복습 과제, 스프링 심화 개선 과제 작성
• 알고리즘 문제 풀기 및 공부