[자료구조와알고리즘with파이썬] ch.6 정렬

책에 나와있는 정렬 중에서도 가장 어려웠던 선택정렬에 대해서 설명해보고자 한다.

---

선택정렬
: 주어진 리스트에서 가장 작은 (또는 큰) 요소를 찾아서 맨 앞에 위치한 요소와 교환하는 과정을 반복하여 정렬을 완성하는 것

 

<선택정렬 예시>

29	10	14	37	13
현재 위치	가장 작은 값

10	29	14	37	13
	현재 위치			가장 작은 값

10	13	14	37	29
		현재 위치, 가장 작은 값

10	13	14	37	29
			현재 위치	가장 작은 값

10	13	14	29	37
				종료

 

---

2751 수 정렬하기2

<자바에서 sort함수를 사용해 오름차순으로 정리>

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        
        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt()); // 하나씩 list에 저장
        }
        
        Collections.sort(list); // 오름차순으로 정리
        
        for (int value : list) {
            sb.append(value).append('\n');
        }
        
        System.out.println(sb);
    }
}

StringBuilder 사용

https://da2uns2.tistory.com/entry/Java-StringBuilder-%EC%82%AC%EC%9A%A9%EB%B2%95%EA%B3%BC-%EC%A3%BC%EC%9A%94-%EB%A9%94%EC%86%8C%EB%93%9C

ArrayList 사용

https://psychoria.tistory.com/765

Arrays.sort (ArrayList는 Collections.sort()를 사용해야 했음)

https://codingnojam.tistory.com/38

---

<파이썬에서 sort함수 사용해서 정렬>

N = int(input()) #N개의 수
numbers = [] #numbers 리스트 초기화

# N개의 숫자를 입력받아 리스트에 저장
for _ in range(N):
    numbers.append(int(input()))

# 리스트를 오름차순으로 정렬 (sort 사용)
numbers.sort()

# 정렬된 리스트 출력
for num in numbers:
    print(num)

---

<파이썬에서 선택정렬 사용해서 정렬하기>

N = int(input())
numbers = []

# N개의 숫자를 입력받아 리스트에 저장
for _ in range(N):
    numbers.append(int(input()))

# !!!선택 정렬 알고리즘 적용!!!
for i in range(len(numbers)): #i는 0부터 1개씩 리스트 길이까지 인덱스 번호 증가
    min_index = i #현재 위치(현재 위치 전은 이미 정렬되었다고 본다.)
    #0번 인덱스에서 시작
    for j in range(i + 1, len(numbers)):
        if numbers[j] < numbers[min_index]:
            min_index = j
    # i번 인덱스 이후에 현재 위치의 값보다 작은 값이 있다면, 가장 작은 값과 현재 위치의 값을 교환
    numbers[i], numbers[min_index] = numbers[min_index], numbers[i]

# 정렬된 리스트 출력
for num in numbers:
    print(num)

---

10989 수 정렬하기3

<파이썬에서 선택정렬로 정렬하기>

N = int(input())
numbers = []

# N개의 숫자를 입력받아 리스트에 저장
for _ in range(N):
    numbers.append(int(input()))

# !!!선택 정렬 알고리즘 적용!!!
for i in range(len(numbers)): #i는 0부터 1개씩 리스트 길이까지 인덱스 번호 증가
    min_index = i #현재 위치(현재 위치 전은 이미 정렬되었다고 본다.)
    #0번 인덱스에서 시작
    for j in range(i + 1, len(numbers)):
        if numbers[j] < numbers[min_index]:
            min_index = j
    # i번 인덱스 이후에 현재 위치의 값보다 작은 값이 있다면, 가장 작은 값과 현재 위치의 값을 교환
    numbers[i], numbers[min_index] = numbers[min_index], numbers[i]

# 정렬된 리스트 출력
for num in numbers:
    print(num)

---

10814 나이순 정렬

<자바에서 선택정렬로 정렬하기>

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[]args){
        try{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String [][] info = new String[N][2];
        for(int i=0; i<N; i++){
            String[] input = br.readLine().split(" ");
            info[i][0] = input[0]; //나이
            info[i][1] = input[1]; //이름
        } //각 줄에 있는 내용을 저장하기
        
        for(int i=0; i<N;i++){ //i가 현재위치
            for(int j=i;j<N;j++){
                if(Integer.parseInt(info[j][0]) < Integer.parseInt(info[i][0])){
                    String[] temp = info[i];
                    info[i] = info[j];
                    info[j] = temp;
                }
            }
        } //선택정렬 사용
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            sb.append(info[i][0]).append(" ").append(info[i][1]).append("\n");
        }
        
        System.out.println(sb.toString());
        }
        
        catch(IOException e){
            System.out.println("입출력 오류가 발생했습니다: " + e.getMessage());
            e.printStackTrace(); // 예외의 상세 정보 출력 (선택 사항)
        }
    }
}

계속 시간초과가 나온다...

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
            String[][] info = new String[N][2];
            
            // 입력을 배열에 저장
            for (int i = 0; i < N; i++) {
                String[] input = br.readLine().split(" ");
                info[i][0] = input[0]; // 나이
                info[i][1] = input[1]; // 이름
            }
            
            // 익명 클래스로 Comparator 정의
            Arrays.sort(info, new Comparator<String[]>() {
                @Override
                public int compare(String[] a, String[] b) {
                    return Integer.parseInt(a[0]) - Integer.parseInt(b[0]);
                }
            });

            // 정렬된 결과 출력
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++) {
                sb.append(info[i][0]).append(" ").append(info[i][1]).append("\n");
            }
            
            System.out.print(sb.toString());
        } catch (IOException e) {
            System.out.println("입출력 오류가 발생했습니다: " + e.getMessage());
            e.printStackTrace();
        }
    }
}

 

Comparator를 사용해줬다. (Chat GPT가 도와줬다.)