opid's document

삽입정렬

- 안정정렬

- 시간복잡도: 

- 설명: 왼쪽에 있는 항목들은 정렬된 것으로 가정하고, 증가하는 인덱스의 값을 삽입하는 방법.

- 특징: 정렬대상이 적거나, 이미 부분적으로 정렬되어 있는 상황일 경우 효율적. 선택정렬과 버블보다는 빠름

문제점

List의 중복된 값을 제거하고 정렬한다. 

해결방안

ArrayList<String> tempList = new ArrayList<String>();
ArrayList<String> dataList;

dataList = new ArrayList<String>(new HashSet<String>(tempList));
Collections.sort(dataList);

2019.10.11. 옛날 코드를 보니 다이아몬드 연산자도 안쓰고, 다형성도 활용하지 않고, 사이드이펙트있는 정렬 메서드 쓰고 있어서... 새로 수정 with 자바8람다

List<String> duplicateStringList = Arrays.asList("2", "2", "1", "3");
List<String> result = duplicateStringList.stream()
.distinct()
.sorted()
.collect(Collectors.toList());

Heap Sort Algorithm Source

package heapSort;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

public class Star {

	public static void main(String args[]) {

		ArrayList<String> data = new ArrayList<String>();
		String file_open_path = "D:/heapData.txt";

		fileRead(file_open_path, data);
		
		System.out.println(data);
		data = heapSort(data);
		System.out.println(data);

	}

	public static ArrayList<String> heapDown(ArrayList<String> data) {
		for (int n = (data.size() / 2) - 1; n >= 0; n--) {
			int leftChild = (n * 2) + 1;
			int rightChild = (n * 2) + 2;

			if (data.get(leftChild).compareTo(data.get(n)) < 0) {
				swapData(data, n, leftChild);
			}

			if (rightChild < data.size()) {
				if (data.get(rightChild).compareTo(data.get(n)) < 0) {
					swapData(data, n, rightChild);
				}
			}
		}
		return data;
	}

	public static ArrayList<String> heapSort(ArrayList<String> data) {
		ArrayList<String> sortedData = new ArrayList<String>();

		int len = data.size();
		data = heapDown(data);

		for (int i = 0; i < len; i++) {
			sortedData.add(0, data.remove(0));
			data = heapDown(data);
		}
		return sortedData;
	}

	private static void fileRead(String path, List<String> data) {
		BufferedReader reader = null;

		if (path != null) {
			try {
				reader = new BufferedReader(new FileReader(path));

				String line = null;
				while ((line = reader.readLine()) != null) {
					if (line.charAt(0) == 65279) {
						data.add(new String(new StringBuffer(line)
								.deleteCharAt(0)));
					} else {
						data.add(line);
					}
				}
				reader.close();
			} catch (Exception e) {
				System.err.println(e);
			} finally {
				try {
					if (reader != null) {
						reader.close();
					}
				} catch (Exception ex) {
				}
			}
		}
	}

	private static void swapData(ArrayList<String> data, int a, int b) {
		String temp;
		temp = data.get(a);
		data.set(a, data.get(b));
		data.set(b, temp);
	}
}