У меня есть задание, в котором я должен реализовать сортировку кучи, быструю сортировку и сортировку в моей программе.В настоящее время у меня нет ошибок, но мой вывод возвращается как ложный для моей кучи и подсчета сортировки.Какие ошибки я делаю?Как их можно исправить?Пожалуйста, помогите оценить любые отзывы.
package sorting;
import java.util.*;
public class Sort2
{
public static int left (int i)
{
return 2 * i + 1;
}
public static int right (int i)
{
return 2 * i + 2;
}
public static int parent (int i)
{
return ((i-1)/2);
}
public static void max_heapify (int[] array, int heap_size, int i)
{
int largest = i;
int l = left(i);
int r = right(i);
if (l < heap_size && array[l] > array[i])
{
largest = l;
}
else
{
largest = i;
}
if (r < heap_size && array[r] > array[largest])
{
largest = r;
}
if (largest != i)
{
int exchange = array[i];
array[i] = array[largest];
array[largest] = exchange;
max_heapify(array, array.length, largest);
}
}
public static int[] build_heap (int[] array)
{
int heap_size = array.length;
for (int i = array.length/2; i >= 1;i--)
{
max_heapify(array, heap_size, i);
}
return array;
}
public static int[] heap_sort (int[] array)
{
build_heap(array);
int heap_size = array.length;
for (int i = array.length;i >= 2;i--)
{
heap_size--;
int exchange = array[0];
array[0] = array[heap_size];
array[heap_size] = exchange;
max_heapify(array, array.length, 1);
}
return array;
}
public static void quick_sort (int[] array, int p, int r)
{
if (p < r)
{
int q = partition(array, p, r);
quick_sort(array, p,q-1);
quick_sort(array, q + 1,r);
}
}
public static int partition (int[] array, int p, int r)
{
int x = array[r];
int i = p - 1;
for (int j = p;j< r;j++)
{
if (array[j] <= x)
{
i++;
int exchange = array[i];
array[i] = array[j];
array[j] = exchange;
}
}
int exchange = array[i+1];
array[i+1] = array[r];
array[r] = exchange;
return i + 1;
}
public static int[] counting_sort (int[] A, int k)
{
int [] C = new int[k+1];
int [] B = new int [A.length];
for(int i = 0;i <= k; i++)
{
C[i] = 0;
}
for(int j = 0; j < A.length; j++)
{
C[A[j]] = C[A[j]] + 1;
}
for (int i = 1; i <= k; i++)
{
C[i] = C[i]+C[i-1];
}
for (int j = A.length - 1;j > 1; j--)
{
B[C[A[j]]- 1]=A[j];
C[A[j]]=C[A[j]] - 1;
}
return B;
}
public static int[] generate_random_array (int n, int k) {
List<Integer> list;
int[] array;
Random rnd;
rnd = new Random(System.currentTimeMillis());
list = new ArrayList<Integer> ();
for (int i = 1; i <= n; i++)
list.add(new Integer(rnd.nextInt(k+1)));
Collections.shuffle(list, rnd);
array = new int[n];
for (int i = 0; i < n; i++)
array[i] = list.get(i).intValue();
return array;
}
public static int[] generate_random_array (int n) {
List<Integer> list;
int[] array;
list = new ArrayList<Integer> ();
for (int i = 1; i <= n; i++)
list.add(new Integer(i));
Collections.shuffle(list, new Random(System.currentTimeMillis()));
array = new int[n];
for (int i = 0; i < n; i++)
array[i] = list.get(i).intValue();
return array;
}
/*
* Input: an integer array
* Output: true if the array is acsendingly sorted, otherwise return false
*/
public static boolean check_sorted (int[] array) {
for (int i = 1; i < array.length; i++) {
if (array[i-1] > array[i])
return false;
}
return true;
}
public static void print_array (int[] array) {
for (int i = 0; i < array.length; i++)
System.out.print(array[i] + ", ");
System.out.println();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int k = 10000;
System.out.println("Heap sort starts ------------------");
for (int n = 100000; n <= 1000000; n=n+100000) {
int[] array = Sort2.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort2.heap_sort(array);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Heap sort ends ------------------");
//Currently works
System.out.println("Quick sort starts ------------------");
for (int n = 100000; n <= 1000000; n=n+100000)
{
int[] array = Sort2.generate_random_array(n);
long t1 = System.currentTimeMillis();
Sort2.quick_sort(array, 0, n-1);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort2.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Quick sort ends ------------------");
int[] array2 = Sort2.generate_random_array(10, 10);
array2 = Sort2.counting_sort(array2,10);
boolean flag = Sort2.check_sorted(array2);
System.out.println(flag);
System.out.println("Counting sort starts ------------------");
for (int n = 100000; n <= 1000000; n=n+100000) {
int[] array = Sort2.generate_random_array(n, k);
long t1 = System.currentTimeMillis();
array = Sort2.counting_sort(array, n);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
flag = Sort2.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Counting sort ends ------------------");
}
}
РЕДАКТИРОВАТЬ Я изменил ваш метод проверки, чтобы распечатать поврежденные элементы массива:
public static boolean check_sorted( int[] array ) {
for( int i = 1; i < array.length; i++ ) {
if( array[i-1] > array[i] ) {
System.err.println( "Reversed array elements: " + (i-1) + "="
+ array[i-1] + ", " + i + "=" + array[i] );
return false;
}
return true;
}
Похоже,Сортировка кучи не сортирует первый элемент массива:
Heap sort starts ------------------
100000,5,false
Reversed array elements: 0=100000, 1=99999
И еще десять таких.