Вниз  Need help with Recursive Bubble Sort Algorithm
- 11.09.2020 / 11:45
#517260
hannah17
  Пользователь
hannah17 
Сейчас: Offline
Hey,

I am trying to implement bubble sort using recursion and have got a response
  1. ArrayIndexOutOfBoundsException: 11
 
Unable to figure out where I went wrong..

  1. public static int[] recBubSort(int []arr, int n){
  2. if(n > arr.length-1){
  3. return arr;
  4. }
  5.  
  6. if(arr[n] > arr[n+1]){
  7. swap(arr,n,n+1);
  8. }
  9. return recBubSort(arr,n+1);
  10. }
  11.  
  12. public static void swap(int arr[], int minPos, int index) {
  13. //System.out.println("SelectionSort SWAP...");
  14. int temp = arr[minPos];
  15. arr[minPos] = arr[index];
  16. arr[index] = temp;
  17. }

- 11.09.2020 / 13:09
#517261
Ксакеп
  Модератор форума
Ксакеп 
Сейчас: Offline
hannah17, hello. You should use some ideas from contract programming. Every function has a contract: a set of preconditions and postconditions that must be completed to ensure the function works as expected.

For swap it may look like this:
– 0 <= minPos <= arr.length - 1
– 0 <= index <= arr.length - 1

Contacts may be applied even to loops or if-conditions:

  1. public static int[] recBubSort(int[] arr, int n) {
  2.   if (n > arr.length - 1) {
  3.     return arr;
  4.   }
  5.   // here n <= arr.length - 1
  6.  
  7.  
  8.   // arr[n + 1] should work,
  9.   // thus n + 1 <= arr.length - 1
  10.   // thus     n <= arr.length - 2
  11.   // but we have n <= arr.length - 1 from the contract above
  12.   if (arr[n] > arr[n + 1]) {
  13.     // indeed, if we have n == arr.length - 1
  14.     // arr[n + 1] === arr[arr.length] – OutOfBounds
  15.     swap(arr, n, n + 1);
  16.   }
  17.  
  18.   return recBubSort(arr, n + 1);
  19. }

- 12.09.2020 / 14:11
#517262
hannah17
  Пользователь
hannah17 
Сейчас: Offline
Awesome, thanks for helping out:)
- 12.09.2020 / 14:19
#517263
hannah17
  Пользователь
hannah17 
Сейчас: Offline
Цитата Ксакеп:
hannah17, hello. You should use some ideas from contract programming. Every function has a contract: a set of preconditions and postconditions that must be completed to ensure the function works as expected.
This site has very well explained the concept of bubble sort:
https://www.interviewbit.com/tutorial/bubble-sort/

Please could you recommend any more resources you've been referring.
- 13.09.2020 / 12:07
#517266
Ксакеп
  Модератор форума
Ксакеп 
Сейчас: Offline
hannah17, no specific resources, sorry :)
Наверх  Всего сообщений: 5
Фильтровать сообщения
Поиск по теме