🌻 JAVA/알고리즘, 자료구조

알고리즘 - 선택 정렬 (Selection Sort)

2021. 11. 21. 23:40
목차
  1. 선택 정렬 (Selection Sort)
  2. 과정
  3. Code
반응형

안녕하세요, 알고리즘을 정리하는 포스팅입니다. 다른 알고리즘을 참고하시려면 해당 카테고리를 이용해주세요. 😊

 

'🌻 JAVA/알고리즘, 자료구조' 카테고리의 글 목록

공부한 것들 정리한 내용을 포스팅합니다.

iseunghan.tistory.com

 

 

선택 정렬 (Selection Sort)

정렬하여 원소를 배치할 자리를 미리 정해놓고, 해당 자리에 넣을 원소를 선택하는 알고리즘입니다.

개인적으로 삽입 정렬과 헷갈린 정렬,, 선택 정렬은 넣을 자리를 미리 지정하고, 삽입 정렬은 1 번째부터 n번째 원소를 앞의 원소와 비교하며 삽입해 나가는 차이가 있다. (헷갈림..)

시간 복잡도 : O(N^2)
공간 복잡도 : O(N)
불안정 정렬

 

과정

 

  1. 먼저 1 번째 자리에 올 원소를 선택할 것입니다. 첫 번째 원소부터 마지막 원소까지 탐색하여 가장 작은 수와 1 번째 수와 위치를 교환합니다.
  2. 이제 2 번째 자리에 올 원소를 선택할 것입니다. 두 번째 원소부터 마지막 원소까지 탐색하여 그 중 제일 작은 수와 위치를 교환합니다.
  3.  위와 동일
  4. 위와 동일
  5. 정렬이 완료됐습니다.

 

Code

  • 먼저 정할 위치의 범위는 첫 번째 위치부터 마지막 - 1 위치까지 입니다.
  • 그 다음 해당 위치에 넣을 원소는 i + 1번째부터 마지막 원소까지 입니다.
int temp, min_idx;

for(int i=0; i<arr.length - 1; i++) {
    min_idx = i;
    
    for(int j=i + 1; j<arr.length; j++) {
        if( arr[min_idx] > arr[j])	min_idx = j;
    }
    temp = arr[i];
    arr[i] = arr[min_idx];
    arr[min_idx] = temp;
}
  • 가장 작은 원소의 위치를 기억하기 위해 min_idx 라는 변수를 이용합니다.
  • 각 범위에 가장 작은 원소를 찾았으면, 위치를 교환해주면 됩니다.
반응형
저작자표시 (새창열림)
  1. 선택 정렬 (Selection Sort)
  2. 과정
  3. Code
'🌻 JAVA/알고리즘, 자료구조' 카테고리의 다른 글
  • 알고리즘 - 버블 정렬 (Bubble Sort)
  • 알고리즘 - 삽입 정렬 (Insertion Sort)
  • 알고리즘 - 퀵 정렬 (Quick-Sort)
  • 자료구조 - 이진탐색 트리 (Binary-Search-Tree)
iseunghan
iseunghan
꾸준하게 열심히..
iseunghan
iseunghan

공지사항

  • 어제보다 나은 오늘이 되기 위해 🔥
  • 분류 전체보기 (262)
    • 💐 Spring (14)
      • 개념 및 이해 (2)
      • Spring 핵심 기술 (24)
      • Spring REST API (8)
      • Spring MVC, DB 접근 기술 (7)
      • Spring Security (23)
      • Spring in Action (1)
    • 🌻 JAVA (84)
      • 자바 ORM 표준 JPA 프로그래밍 (20)
      • 알고리즘, 자료구조 (13)
      • 디자인 패턴 (7)
      • 정리정리정리 (43)
      • JUnit (1)
    • 🔖 Snippets (3)
      • Javascript (3)
    • ⚙️ Devops (22)
      • ⛏ Git (11)
      • 🐳 Docker (6)
      • 🐧 Linux (3)
      • 🌈 Jenkins (1)
      • 📬 Kafka (1)
    • 💬 ETC.. (4)
      • 💻 macOS (2)
    • 🌧️ ORM (2)
      • JPA (2)
    • 🐍 Python (3)
    • 📚 Databases (15)
      • 오라클로 배우는 데이터베이스 개론과 실습(2판) (3)
      • RealMySQL 8.0 (8)
    • 🔥 Computer Science (5)
      • 📡 네트워크 (5)
    • 🏷️ 협업 (1)
    • 📜 코딩테스트 (38)
      • BAEKJOON\수학 1, 수학 2 (8)
      • BAEKJOON\재귀 (5)
      • BAEKJOON\브루트 포스 (3)
      • BAEKJOON\정렬 (1)
      • BAEKJOON\백트래킹 (5)
      • BAEKJOON\BFS, DFS (6)
      • BAEKJOON\이분탐색 (1)
      • BAEKJOON\다이나믹 프로그래밍 (9)
      • BAEKJOON\그리디 알고리즘 (0)
    • ✨ ISEUNGHAN (1)

인기 글

최근 글

전체
오늘
어제
반응형
hELLO · Designed By 정상우.
iseunghan
알고리즘 - 선택 정렬 (Selection Sort)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.