버블정렬(bubble sort) 구현하기

버블정렬은 큰 값이 하나씩 뒤로 위치하게 하는 정렬을 의미한다

→ 두 값을 비교해서 기준에 따른 값 배치를 몇 번 반복할지를 정하는 로직을 구현해야하는 버블정렬

String[] strings = {"sun", "bed", "car", "book"};
int position = 1;

...

for(int n = 0; n < strings.length - 1; n++) {
	// 1회차 - strings.length: 4, strings.length-1: 3, n: 0

    for(int j = 0; j < strings.length - 1 - n; j++) {
    	// 1) n: 0, j: 0, j < strings.length-1-0 -> 0 < 3,        
        // c1 = strings[0].charAt(1); --> c1 = "sun".charAt(1);
        // c1 = 'u';
        
        // 2) n: 0, j: 1, j < strings.length-1-0 -> 1 < 3,
		// c1 = strings[1].charAt(1); "sun".charAt(1); c1 = 'u';
        // c2 = strings[1+1].charAt(1); "car".charAt(1); c2 = 'a';
        
       	char c1 = strings[j].charAt(n);
        // c2 = strings[0+1].charAt(1); 
        // c2 = "bed".charAt(1); -> c2 = 'e';
        char c2 = strings[j+1].charAt(n);
        
        if(c1>c2) // 'u'>'e'
        {
        	String temp = strings[j];
            strings[j] = strings[j+1];
            strings[j+1] = temp;
        }
    }	
}

 

버블정렬의 핵심은 매 반복마다 맨 끝부터 하나씩 정렬된 상태가 된다는 것.

 

문자열 내 마음대로 정렬하기 알고리즘 문제를 버블정렬로 구현함

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12915

package algo2025.september.seventeenth;

import jdk.internal.joptsimple.internal.Strings;

/*
* @param strings: String[], n: int
* 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하는 기능
* ex. String[] strings = ["sun", "bed", "car"]이고,
* n = 1, 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings 가 정렬되어
* @return ["car", "bed", "sun"]
*/


public class Temp {
    public String[] solution(String[] strings, int n) {
        // 버블정렬 구현하기
        for(int outIndex = 0; outIndex < strings.length - 1; outIndex++) {
            for(int innerIndex = 0; innerIndex < strings.length - 1 - outIndex; innerIndex++) {
                char c1 = strings[innerIndex].charAt(n);
                char c2 = strings[innerIndex + 1].charAt(n);

                // strings[innerIndex].compareTo(strings[innerIndex+1])>0 의 경우,
                // strings[innerIndex] 가 strings[innerIndex+1] 보다 사전순으로 더 나중에 온다는 말
                // 즉 strings[innerIndex+1], strings[innerIndex] 이렇게 배치되게 만들어야 한다는 것.
                if(c1>c2 || (c1 == c2) && strings[innerIndex].compareTo(strings[innerIndex+1]) > 0) {
                    String temp = strings[innerIndex];
                    strings[innerIndex] = strings[innerIndex+1];
                    strings[innerIndex+1] = temp;
                }
            }
        } return strings;
    }
    /* 부분적으로만 정렬이 이루어지는 제한적인 로직
    public String[] solution(String[] strings, int n) {
        // 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.
        // ["sun", "bed", "car"]
        String firstString = strings[0]; // String s0 = "sun";
        System.out.println("1. String firstString = strings[0]; firstString: "+firstString);

        for(int index = 1; index < strings.length; index++) {
            // string[1].charAt(1); bed 의 e 가 c1 에 대입
            // c1 = 'e';
            char c1 = strings[index].charAt(n);
            System.out.println("2. char c1 = strings[index].charAt(n); c1: "+c1);


            // char 타입 c 가 c1 보다 크다는 의미,
            // firstString.charAt(1) --> u, u>e
            if(firstString.charAt(n)>c1) {
                String temp = firstString;
                System.out.println("3. String temp = firstString; temp: "+temp);

                strings[index-1] = strings[index]; // strings[0] = strings[1];
                strings[index] = temp;
                System.out.println("4. strings[index] = temp; string[index]: "+strings[index]);
            } firstString = strings[index];
            System.out.println("5. firstString = strings[index]; firstString: "+firstString);

        } return strings;
    } */
}

 

refactoring

public class Temp {
    public String[] solution(String[] strings, int n) {
        return sortByCharAtIndexThenLexical(strings, n);
    }

    private String[] sortByCharAtIndexThenLexical(String[] strings, int n) {
        for(int i = 0; i < strings.length - 1; i++) {
            for(int j = 0; j < strings.length - 1 - i; j++) {
                if(shouldSwap(strings[j], strings[j+1], n))
                    swap(strings, j);
            }
        } return strings;
    }

    private boolean shouldSwap(String a, String b, int n) {
        char c1 = a.charAt(n);
        char c2 = b.charAt(n);

        return (c1 > c2) || ((c1 == c2) && (a.compareTo(b) > 0));
    }

    private void swap(String[] strings, int j) {
        String temp = strings[j];
        strings[j] = strings[j +1];
        strings[j +1] = temp;
    }
}

 

후기

chatgpt의 도움을 많이 받았던 문제, for문의 조건문 이해에서 많은 시간을 할애했다.

수기로 하나하나 대입하며 흐름 이해에 중점을 두었다.