-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathShiftSort.java
More file actions
168 lines (145 loc) · 5.01 KB
/
ShiftSort.java
File metadata and controls
168 lines (145 loc) · 5.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/*
* Copyright (C) 2017 James Quintero
*/
import java.util.*;
import java.io.*;
//Hold the latest version of Shift Sort
public class ShiftSort
{
public ShiftSort()
{
}
//ShiftSortV10
public void sort(int[] array)
{
//gets indexes of array that indicate the start of sorted sublists
//Old versions of Shift Sort had a list of 0s and 1s that indicate where in the array the elements were out of order.
//A 0 meant the value at the current index was less than the value at the previous index, and was therefore out of order. A 1 meant they were in order
int[] zero_indices = new int[(int)(array.length/2)+2];
zero_indices[0]=array.length;
//tracks the index of the last added value in zero_indices
int end_tracker=1;
//stops at x<1 because 0 being a zero_index is a given
for(int x = array.length-1; x >= 1; x--)
{
//if cur index is out of order
if(array[x]<array[x-1])
{
//if lower index is also out of order, then swap
if(x>1 && array[x-1] < array[x-2])
{
//swaps array elements
int temp = array[x-2];
array[x-2] = array[x];
array[x] = temp;
if( x != array.length-1)
{
if(array[x+1]<array[x])
{
zero_indices[end_tracker]=x+1;
end_tracker++;
}
}
}
else
{
zero_indices[end_tracker] = x;
end_tracker++;
}
//skips
x--;
}
}
//merges sorted lists specified by zero_indices
split(array, zero_indices, 0, end_tracker);
}
//splits zero_indices into sublists of indices in array
public void split(int[] array, int[] zero_indices, int i, int j)
{
//if have exactly 3 indices, then merge the 2 lists
if( (j-i)==2)
{
merge(array, zero_indices[j], zero_indices[j-1], zero_indices[i]);
return;
}
//2 indices or less, just return, because not enough to merge
else if( (j-i)<2)
return;
//at this point, have >3 items, so split in half again
int new_j = i + (j-i)/2;
int new_i = new_j+1;
//continues splitting first half
split(array, zero_indices, i, new_j);
//continues splitting second half
split(array, zero_indices, new_i, j);
//merges first half
merge(array, zero_indices[new_i], zero_indices[new_j], zero_indices[i]);
//merges second half
merge(array, zero_indices[j], zero_indices[new_i], zero_indices[i]);
}
//merges from the back to front
public void merge(int[] array, int first_index, int second_index, int third_index)
{
//if first_list>second_list, have second list be the list that gets merged into the first list
if(second_index-first_index > third_index-second_index)
{
//gets 2nd list
int[] temp_2nd = new int[third_index-second_index];
int counter=0;
for(int y =second_index; y < third_index; y++)
{
temp_2nd[counter]=array[y];
counter++;
}
//starts off at length of 2nd list
int second_counter=third_index-second_index;
int left=second_index-1;
while(second_counter>0)
{
//shift if left is greater than right
if(left>=first_index && array[left]>=temp_2nd[second_counter-1])
{
array[left+second_counter]=array[left];
left--;
}
//add from 2nd if greater than left
else
{
array[left+second_counter]=temp_2nd[second_counter-1];
second_counter--;
}
}
}
else
{
//gets 1st list
int[] temp_1st = new int[second_index-first_index];
int counter=0;
for(int y =first_index; y < second_index; y++)
{
temp_1st[counter]=array[y];
counter++;
}
//starts off at length of 2nd list
int first_counter=0;
int temp_length = second_index-first_index;
int right=second_index;
while(first_counter< temp_1st.length)
{
//shift if left is greater than right
if(right<third_index && array[right]<temp_1st[first_counter])
{
array[right-temp_length]=array[right];
right++;
}
//add from 2nd if greater than left
else
{
array[right-temp_length]=temp_1st[first_counter];
first_counter++;
temp_length--;
}
}
}
}
}