Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sorting algorithms in Java
package com.test.app;
import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
int[] array = {10,8,6,4,2,9,7,5,3,1};
SortUtil.quickSort(array, 0, 9);
System.out.println(Arrays.toString(array));
}
}
package com.test.app;
class SortUtil{
//Bubble sort
public static void bubbleSort(int[] array) {
for(int i = array.length - 1; i > 0; i--){
for(int n = 0; n < i; n++){
if(array[n] > array[n+1]){
int tmp = array[n];
array[n] = array[n+1];
array[n+1] = tmp;
}
}
}
}
//Insertion sort
public static void insertionSort(int[] array) {
for(int i = 1; i < array.length; i++){
int temp = array[i];
int k = i-1;
while(k >= 0 && temp < array[k]){
array[k+1] = array[k];
k--;
}
array[k+1] = temp;
}
}
//Selection sort
public static void selectionSort(int[] array) {
for(int i = 0; i < array.length; i++) {
int n = i + 1;
int min = i;
while(n < array.length){
if(array[n] < array[min]){
min = n;
}
n++;
}
int temp = array[min];
array[min] = array[i];
array[i] = temp;
}
}
//Merge sort
public static void mergeSort(int[] array, int[] tempArray, int left, int right) {
int mid = (left + right) / 2;
if(left < right) {
mergeSort(array, tempArray, left, mid);
mergeSort(array, tempArray, mid + 1, right);
merge(array, tempArray, left, mid, right);
}
}
public static void merge(int[] array, int[] tempArray, int lMin, int lMax, int rMax) {
int tempIdx= lMin;
int n = lMin;
int rMin = lMax + 1;
while(lMin <= lMax && rMin <= rMax){
if(array[lMin] <= array[rMin]){
tempArray[tempIdx++] = array[lMin++];
}
else {
tempArray[tempIdx++] = array[rMin++];
}
}
while(lMin <= lMax){
tempArray[tempIdx++] = array[lMin++];
}
while(rMin <= rMax){
tempArray[tempIdx++] = array[rMin++];
}
while(n <= rMax){
array[n] = tempArray[n++];
}
}
//Shell sort
public static void shellSort(int[] array) {
int h = 1;
while(h <= array.length/3) {
h = h*3 + 1;
}
while(h > 0) {
for(int i = h; i < array.length; i++) {
int temp = array[i];
int idx = i;
while(idx > h-1 && array[idx-h] >= temp) {
array[idx] = array[idx-h];
idx -= h;
}
array[idx] = temp;
}
h = (h - 1) / 3;
}
}
//Quick sort
public static void quickSort(int array[], int begin, int end) {
if(begin < end) {
int pivotIdx = partition(array, begin, end);
quickSort(array, begin, pivotIdx - 1);
quickSort(array, pivotIdx + 1, end);
}
}
public static int partition(int array[], int begin, int end) {
int pivot = array[end];
int i = begin;
while(i < end) {
if(array[i] <= pivot) {
if(i != begin) swap(array, begin, i);
begin++;
}
i++;
}
swap(array, begin, end);
return begin;
}
public static void swap(int array[], int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment