Утверждение, выбор и быстрая сортировка - PullRequest
Новая
       31

Утверждение, выбор и быстрая сортировка

0 голосов
/ 02 апреля 2019

Проблема заключается в следующем:

Всего n целых чисел в диапазоне от 0 до n - 1 случайно хранятся в A, массиве размера n.Вы должны реализовать следующие четыре алгоритма сортировки кандидатов для сортировки A: сортировка вставкой, сортировка выбора и быстрая сортировка.Обратите внимание, что важно, чтобы вы работали непосредственно с указанным начальным кодом. Прочитайте начальный код и убедитесь, что вы понимаете, как он работает, прежде чем пытаться изменить его.Разработайте модификации стартового кода для методов, описанных в разделе «Введение».

Initially, the array is:
0 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
.............................
90 91 92 93 94 95 96 97 98 99

After randomization, the array becomes:
91 54 53 47 86 2 51 99 52 31
60 15 59 43 56 78 32 10 12 70
33 34 11 96 92 66 4 88 41 22
85 18 23 57 24 83 35 44 5 68
48 79 46 71 42 82 25 29 30 21
27 94 20 6 84 73 77 81 28 38
75 89 39 36 45 62 65 1 49 87
50 67 90 40 55 93 64 19 0 61
37 8 69 98 3 16 9 58 97 63
80 95 7 74 26 72 14 76 13 17

The array is now sorted:
0 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

Теперь я знаю, как работает код вставки.Я прочитал много уроков и сделал несколько примеров.С этим вопросом я не совсем уверен, как делается код вставки.Как базовая сортировка вставок будет выглядеть следующим образом: следует : 

class InsertionSort { 
/*Function to sort array using insertion sort*/
void sort(int arr[]) 
{ 
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
        int key = arr[i]; 
        int j = i - 1; 

        /* Move elements of arr[0..i-1], that are 
        greater than key, to one position ahead 
        of their current position */
        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 

/* A utility function to print array of size n*/
static void printArray(int arr[]) 
{ 
    int n = arr.length; 
    for (int i = 0; i < n; ++i) 
        System.out.print(arr[i] + " "); 

    System.out.println(); 
} 

// Driver method 
public static void main(String args[]) 
{ 
    int arr[] = { 12, 11, 13, 5, 6 }; 

    InsertionSort ob = new InsertionSort(); 
    ob.sort(arr); 

    printArray(arr); 
  } 
}

Код, который мне дали: 

import java.util.Random;

public class Sort {
 // swap the ith element with the jth elements.
 private void  swap(int[] a, int i, int j){
  int temp; 
  temp = a[i]; a[i] = a[j]; a[j] = temp;
 }
 // initialize the array a with elements from 0 to size-1. 
 public void  initializeArray(int[] a, int size){
  for (int i=0; i<size; i++){
   a[i]=i;
  }
 }

 // display the elements in the array a, 10 elements per row. 
 public void  displayArray(int[] a, int size){
  for (int i=0; i<size; i++){
   if(i%10==0){
    System.out.println();
   }
   System.out.print(a[i]+ " ");
  }
  System.out.println();
 }

  // randomly swap two elements in array a for SWAPTIMES times. 
  public void randomizeArray(int[] a, int size){
  final int SWAPTIMES = 10000;
  Random r = new Random();
        int j, k;
        for(int i=0; i< SWAPTIMES; i++){
         j = r.nextInt(size);
         k = r.nextInt(size);
         this.swap(a,  j, k);
        }
  }


  // **insertionSort**. 
  public void  insertionSort(int[] a, int size){
     for (int i = 1; i < a.length; i++)
  {
  int next = a[i];
  // Move all larger elements up
  int j = i;
  while (j > 0 && a[j - 1] > next)
  {
    a[j] = a[j - 1];
    j--;      }
    // Insert the element
  a[j] = next;
     }
  }


 // **selectionSort**
 public void selectionSort(int a[], int size){
     //your code here.
 }

 // **quickSort**
 public  void quickSort(int[] a, int size)
    {
     //your code here. for this method, you are suggested to write 
  // additional helper methods as appropriate on top of quickSort. 

    }     
}

Любая помощьдля начала я был бы признателен.

...