선택 정렬

아래 강의를 보면서 연습하고 기록하고 있습니다

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

문제

코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int inputLength = sc.nextInt();

		int[] inputInts = new int[inputLength];
		for (int i = 0; i < inputLength; i++) {
			inputInts[i] = sc.nextInt();
		}

		for (int i = 0; i < inputLength - 1; i++) {
			int minIdx = i; // 가장 낮은 값의 idx를 저장 할 변수
			for (int j = i + 1; j < inputLength; j++) {
				if (inputInts[j] < inputInts[minIdx]) // 현재 루프의 값이 가장 낮의 값의 idx를 저장할 인덱스의 값보다 작은경우
					minIdx = j; // 가장 낮의 값의 idx를 현재 j의 값으로 치환
			}
			// 스왑
			int tmp = inputInts[i];
			inputInts[i] = inputInts[minIdx];
			inputInts[minIdx] = tmp;
		}

		for (int i : inputInts) {
			System.out.print(i + " ");
		}

	}

}

 

개념설명

선택 정렬(selection sort) 알고리즘 개념 요약

• 
  제자리 정렬(in-place sorting) 알고리즘의 하나
  입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
  해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
  첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
  두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
• 과정 설명
  주어진 배열 중에서 최솟값을 찾는다.
  그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
  맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
  하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
  https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html