sort

 

 

---

성능

 

 

---

 

buble sort

 

import java.util.Arrays;

public class BubbleSortExample {

    public static void main(String[] args) {
        int[] nums = {9, 3, 5, 7, 1};
        bubbleSort(nums);

        // 정렬 결과 출력
        System.out.println(Arrays.toString(nums));
    }

    public static void bubbleSort(int[] nums) {
        int n = nums.length;

        // Bubble Sort 알고리즘
        for (int idx = 0; idx < n - 1; idx++) {
            for (int i = 0; i < n - idx - 1; i++) {
                if (nums[i] > nums[i + 1]) {
                    // Swap
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                }
            }
        }
    }
}

 

[1, 3, 5, 7, 9]

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BubbleSortPairs {

    public static void main(String[] args) {
        // 입력 데이터 초기화
        List<Pair> numStrs = new ArrayList<>(Arrays.asList(
            new Pair(7, "a"),
            new Pair(5, "a"),
            new Pair(5, "b"),
            new Pair(7, "b"),
            new Pair(3, "c")
        ));

        // 정렬 실행
        bubbleSort(numStrs);

        // 결과 출력
        for (Pair pair : numStrs) {
            System.out.println("(" + pair.num + ", " + pair.str + ")");
        }
    }

    public static void bubbleSort(List<Pair> numStrs) {
        int n = numStrs.size();

        // Bubble Sort 알고리즘
        for (int idx = 0; idx < n - 1; idx++) {
            for (int i = 0; i < n - idx - 1; i++) {
                if (numStrs.get(i).num > numStrs.get(i + 1).num) {
                    // Swap
                    Pair temp = numStrs.get(i);
                    numStrs.set(i, numStrs.get(i + 1));
                    numStrs.set(i + 1, temp);
                }
            }
        }
    }

    // Pair 클래스 정의
    static class Pair {
        int num;
        String str;

        public Pair(int num, String str) {
            this.num = num;
            this.str = str;
        }
    }
}

 

[(3, 'c'), (5, 'a'), (5, 'b'), (7, 'a'), (7, 'b')]

 

---

insertion sort

package collection.sort;

import java.util.ArrayList;
import java.util.List;

public class InsertionSort {

    public static void insertionSort(int[] numArr) {
        // 배열의 두 번째 요소부터 시작 (첫 번째 요소는 이미 정렬되어 있다고 가정)
        for (int choicedIndex = 1; choicedIndex < numArr.length; choicedIndex++) {
            int choicedValue = numArr[choicedIndex];  // 현재 정렬할 값
            int beforeIndex = choicedIndex - 1;    // 현재 위치를 기준으로 왼쪽으로 이동하며 비교

            // 값이 왼쪽의 값보다 작은 경우, 한 칸씩 오른쪽으로 밀어낸다.
            while (beforeIndex >= 0 && choicedValue < numArr[beforeIndex]) {
                numArr[beforeIndex + 1] = numArr[beforeIndex];  // 한 칸씩 오른쪽으로 밀기
                beforeIndex = beforeIndex - 1;  // 왼쪽으로 이동
            }

            // 적절한 위치에 choicedValue 값을 삽입
            numArr[beforeIndex + 1] = choicedValue;
        }
    }

    public static List<Integer> insertionSort(List<Integer> numList) {
        // numList 두 번째 요소부터 시작 (첫 번째 요소는 이미 정렬되어 있다고 가정)
        for (int choicedIndex = 1; choicedIndex < numList.size(); choicedIndex++) {
            int choiceValue = numList.get(choicedIndex);
            int beforeIndex = choicedIndex - 1;

            // choiceValue가 이전 값보다 작은 경우, 한 칸씩 오른쪽으로 밀어낸다.
            while (beforeIndex >= 0 && choiceValue < numList.get(beforeIndex)) {
                numList.set(beforeIndex + 1, numList.get(beforeIndex));
                beforeIndex = beforeIndex - 1;
            }

            /// 적절한 위치에 choicedValue 값을 삽입
            numList.set(beforeIndex + 1, choiceValue);
        }
        return numList;
    }


    public static void main(String[] args) {
        // 예시 배열
        int[] nums = {9, 3, 5, 7, 1};

        // 정렬 호출
        insertionSort(nums);

        // 결과 출력
        System.out.print("Sorted Array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }


        List<Integer> sortedNums = insertionSort(new ArrayList<>(List.of(9, 3, 5, 7, 1)));
        System.out.println(sortedNums);
    }
}

selection sort

package collection.sort;

import java.util.ArrayList;
import java.util.List;

public class SelectionSort {
    public static void main(String[] args) {
        // num_strs 배열 초기화
        List<Pair> numStrs = new ArrayList<>();
        numStrs.add(new Pair(7, "a"));
        numStrs.add(new Pair(7, "b"));
        numStrs.add(new Pair(5, "a"));
        numStrs.add(new Pair(5, "b"));
        numStrs.add(new Pair(3, "c"));

        // 정렬 실행
        List<Pair> sortedList = sort(numStrs);

        // 결과 출력
        for (Pair pair : sortedList) {
            System.out.println("(" + pair.num + ", " + pair.str + ")");
        }
    }

    public static List<Pair> sort(List<Pair> numStrs) {
        for (int idx = 0; idx < numStrs.size(); idx++) {
            int minNum = numStrs.get(idx).num;
            int minIdx = idx;

            for (int i = idx; i < numStrs.size(); i++) {
                if (numStrs.get(i).num < minNum) {
                    minNum = numStrs.get(i).num;
                    minIdx = i;
                }
            }

            // Swap
            Pair temp = numStrs.get(idx);
            numStrs.set(idx, numStrs.get(minIdx));
            numStrs.set(minIdx, temp);
        }
        return numStrs;
    }

    // Pair 클래스 정의
    static class Pair {
        int num;
        String str;

        public Pair(int num, String str) {
            this.num = num;
            this.str = str;
        }
    }
}

 

 

---

merge sort

package collection.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeSort {
    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(5, 7, 9, 3, 1, 2, 4);
        List<Integer> sortedNums = mergeSort(nums);

        // 결과 출력
        System.out.println(sortedNums);
    }

    public static List<Integer> mergeSort(List<Integer> nums) {
        // 리스트 길이가 1이면 정렬 완료된 것으로 간주
        int length = nums.size();
        if (length == 1) {
            return nums;
        }

        // 리스트를 두 부분으로 나눔
        int mid = length / 2;
        List<Integer> leftNums = nums.subList(0, mid);
        List<Integer> rightNums = nums.subList(mid, length);

        // 재귀적으로 정렬
        List<Integer> sortedLeft = mergeSort(leftNums);
        List<Integer> sortedRight = mergeSort(rightNums);

        // 두 정렬된 리스트를 병합
        return merge(sortedLeft, sortedRight);
    }

    public static List<Integer> merge(List<Integer> left, List<Integer> right) {
        List<Integer> sortedNums = new ArrayList<>();
        int idxL = 0, idxR = 0;

        // 병합
        while (idxL < left.size() || idxR < right.size()) {
            if (idxL == left.size()) {
                sortedNums.add(right.get(idxR));
                idxR++;
                continue;
            }

            if (idxR == right.size()) {
                sortedNums.add(left.get(idxL));
                idxL++;
                continue;
            }

            if (right.get(idxR) <= left.get(idxL)) {
                sortedNums.add(right.get(idxR));
                idxR++;
            } else {
                sortedNums.add(left.get(idxL));
                idxL++;
            }
        }

        return sortedNums;
    }
}

quick select

package collection.sort;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class QuickSelect {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(5, 7, 9, 3, 1, 2, 4));
        int k = 2; // k번째로 큰 숫자
        int result = quickSelect(nums, k);
        System.out.println("The " + k + "th largest element is: " + result);
    }

    public static int quickSelect(List<Integer> nums, int k) {
        int length = nums.size();

        // 리스트에 하나의 요소만 있다면 그대로 반환
        if (length == 1) {
            return nums.get(0);
        }

        // 랜덤 피벗 선택
        Random random = new Random();
        int pivotIdx = random.nextInt(length);
        int lastIdx = length - 1;

        // 피벗을 리스트의 마지막으로 이동
        swap(nums, pivotIdx, lastIdx);

        int leftIdx = 0;
        int rightIdx = length - 2;
        int pivot = nums.get(lastIdx);

        // 파티셔닝
        while (leftIdx <= rightIdx) {
            if (nums.get(leftIdx) <= pivot) {
                leftIdx++;
                continue;
            }

            if (nums.get(rightIdx) > pivot) {
                rightIdx--;
                continue;
            }

            if (nums.get(leftIdx) > pivot && nums.get(rightIdx) <= pivot) {
                swap(nums, leftIdx, rightIdx);
                continue;
            }
        }

        // 피벗을 올바른 위치로 이동
        swap(nums, leftIdx, lastIdx);

        // k번째로 큰 숫자를 찾기 위해 재귀 호출
        if (leftIdx == length - k) {
            return nums.get(leftIdx);
        } else if (leftIdx < length - k) {
            return quickSelect(nums.subList(leftIdx + 1, length), k);
        } else {
            return quickSelect(nums.subList(0, leftIdx), k - (length - leftIdx));
        }
    }

    // 두 리스트 요소를 교환
    private static void swap(List<Integer> nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }
}

 

 

---

quick sort

 

 

---

heap sort

package collection.sort;

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class HeapSort {
    public static void main(String[] args) {
        int[] nums = {3, 5, 7, 9, 4, 2};
        int[] sortedNums = heapSort(nums);

        // 결과 출력
        for (int num : sortedNums) {
            System.out.print(num + " ");
        }
    }

    public static int[] heapSort(int[] nums) {
        // 최대 힙 구현
        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 힙에 요소 추가
        for (int num : nums) {
            maxHeap.offer(num);
        }

        // 정렬된 배열에 요소 추가 (큰 값부터 작은 값 순서)
        int[] sorted = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            sorted[i] = maxHeap.poll(); // 최대값 제거
        }

        return sorted;
    }
}

 

 

---

counting sort

 

 

radix sort

 

 

 

import java.util.ArrayList;
import java.util.List;

public class RadixSort {
    public static List<Integer> countingSortByDigit(List<Integer> nums, int digit) {
        int[] counts = new int[10];
        int digitPlace = (int) Math.pow(10, digit);

        // Count the occurrences of each digit at the current place
        for (int num : nums) {
            int countIndex = (num / digitPlace) % 10;
            counts[countIndex]++;
        }

        // Compute accumulated counts for placement
        int[] accCounts = new int[10];
        int accCount = 0;
        for (int i = 0; i < counts.length; i++) {
            accCount += counts[i];
            accCounts[i] = accCount;
        }

        // Determine end locations for each digit
        int[] endLocs = new int[10];
        for (int i = 0; i < accCounts.length; i++) {
            endLocs[i] = accCounts[i] - 1;
        }

        // Place the numbers into the sorted array
        List<Integer> sorted = new ArrayList<>(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            sorted.add(0);
        }

        for (int i = nums.size() - 1; i >= 0; i--) {
            int num = nums.get(i);
            int countIndex = (num / digitPlace) % 10;
            int endLoc = endLocs[countIndex];
            sorted.set(endLoc, num);
            endLocs[countIndex]--;
        }

        return sorted;
    }

    public static List<Integer> radixSort(List<Integer> nums) {
        int largestNum = nums.stream().max(Integer::compareTo).orElse(0);
        int digits = (int) Math.log10(largestNum) + 1;

        List<Integer> sorted = new ArrayList<>(nums);
        for (int digit = 0; digit < digits; digit++) {
            sorted = countingSortByDigit(sorted, digit);
        }

        return sorted;
    }

    public static void main(String[] args) {
        List<Integer> nums = List.of(391, 582, 50, 924, 8, 192);
        List<Integer> sorted = radixSort(nums);
        System.out.println(sorted);
    }
}