kkkkkkkkkkkk
kkkkk
kkkkkkkkkkkk
전체 방문자
오늘
어제
  • 분류 전체보기
    • CS & OS
    • Algorithms
    • Laguage
    • Book
      • 객체지향의 사실과 오해
      • Effective Java
      • Spring boot 와 AWS로 혼자 구현하는 ..
      • 도메인 주도 계발 시작하기
    • DB
    • Spring
    • Spring Boot
    • JPA
    • Git
    • Clean Code
    • HTTP

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 역할
  • 설계 원칙
  • 책임
  • 객체지향 프로그래밍
  • 응집도
  • 결합도

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
kkkkkkkkkkkk

kkkkk

Algorithms

[Sort] 선택 정렬 (Selection Sort)

2022. 6. 26. 22:52

소개

  • 리스트 안의 자료중 가장 작은수 또는 가장 큰수를 찾아 첫 번째 위치 또는 가장 마지막 위치의 수와 교환해주는 정렬이다.
  • 교환 횟수를 최소화하는 반면 비교하는 횟수는 증가한다.

 

동작원리

  • 배열의 순서와 상관 없이 선택 정렬되는 배열은 n -1 의 교환이 이루어진다.
  • 버블 정렬 보다 교환 횟수는 적어지지만 비교를 모든 원소를 해야하기 때문에 n2의 비교가 이루어진다.
for (int i = 0; i < arr.length; i++) {
    int minIndex = i;
    for (int j = i; j < arr.length; j++) {
        if (arr[minIndex] < arr[j]) {
            continue;
        }
        minIndex = j;
    }
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

 

버블 정렬 vs 선택 정렬

대규모의 데이터를 처리한다고 가정해보자.

두개의 인접한 숫자를 n-1 번 실행하여 정렬하는 것보단 임의의 숫자를 정의하여 차례대로 비교하는 것이 훨씬 빠를것이다.

'Algorithms' 카테고리의 다른 글

[Sort] 퀵 정렬 (Quick Sort)  (0) 2022.06.26
[Sort] 병합 정렬 (Merge Sort)  (0) 2022.06.26
[Sort] 셸 정렬 (Shell Sort)  (0) 2022.06.26
[Sort] 삽입 정렬 ( Insertion Sort)  (0) 2022.06.26
[Sort] 버블 정렬 (Bubble Sort)  (0) 2022.06.26
[Sort] 선형 탐색 (Linear Search)  (0) 2022.06.26
[JAVA] 해싱 동작 방식  (0) 2022.01.17
[JAVA] 성능을 개선한 Map 구현 (해싱)  (0) 2022.01.17
    'Algorithms' 카테고리의 다른 글
    • [Sort] 셸 정렬 (Shell Sort)
    • [Sort] 삽입 정렬 ( Insertion Sort)
    • [Sort] 버블 정렬 (Bubble Sort)
    • [Sort] 선형 탐색 (Linear Search)
    kkkkkkkkkkkk
    kkkkkkkkkkkk

    티스토리툴바