삽입정렬

- 안정정렬

- 시간복잡도: 

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

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



'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 병합정렬(MergeSort)  (0) 2015.10.30
[JAVA] 버블정렬(BubbleSort)  (0) 2015.10.23
[JAVA] 선택정렬(SelectionSort)  (0) 2015.10.09
[JAVA] 쉘정렬(ShellSort)  (0) 2015.10.02

 실행환경

 Desktop

 조립식

 CPU

 Intel(R) Core(TM) i7-3770 3.50GHz

 Memory

 4 GB

 OS

 Window 7 Professional 32bit

 Java

 1.7.0_51

 Android

 SDK : 4.4.2 (KitKat), Google APIs 4.4.2

 TEST : Galaxy S3 4.3(Jelly Bean)

 WebServer

 Apache Tomcat 7.0

 DB

 MySQL 5.6.15


문제점

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);
	}
}


+ Recent posts