Custom sorting algo / optimized bubble sort

Question

I'm a novice and started diving into data structures and algorithms recently. I was taught bubble sort recently and I found that the original bubble sort algorithm is so inefficient, so I wrote a modified, yet simple version of it.

Algorithm:

1. Loop through the provided array and store the index of the max element
2. Swap the last element with the max element
3. Decrease the total looping length by 1 and repeat

Code:

import java.util.Scanner;
class Methods extends Main
 {
 int[] getArray(int len)
 {
 int[] array = new int[len];
 for (int i = 0; i < array.length; i++)
 {
 array[i] = sc.nextInt();
 }
 return array;
 }
 int [] pushMaxSort(int[] arr)
 {
 int len = arr.length;
 while (len>0)
 {
 int max=arr[0];
 int index=0;
 for(int i=0; i<len;i++)
 {
 if(arr[i]>max)
 {
 max = arr[i];
 index = i;
 }
 }
 int temp = arr[len-1];
 arr[len-1] = arr[index];
 arr[index] = temp;
 len--;
 }
 return arr;
 }
 void printArr(int []arr)
 {
 System.out.println("sorted array :");
 for(int i=0;i<arr.length;i++)
 {
 System.out.print("\t" +arr[i]);
 }
 }
 }
class Main
 {
 static Scanner sc = new Scanner(System.in);
 public static void main(String[] args)
 {
 long t = System.currentTimeMillis();
 Methods o = new Methods();
 o.printArr(o.pushMaxSort(o.getArray(sc.nextInt())));
 long t2 = System.currentTimeMillis();
 System.out.println("\n\n time " + (t2-t));
 }
 }

Also, I need to learn to describe complexity (using Big O notation). I am vaguely guessing this has \$O(n \log{n})\$ but please let me know of the exact running time.

• Betlista: Once you have code it is typically simple to see what the complexity is. You have for loop in while loop, which in worst case run with whole length => O(n^2). Sure, it's 0.5 * n^2 but we still say it's O(n^2)...
• Simon Forsberg: Just to be clear, by "DS", do you mean "data structures"? If so, then write "data structures". Don't assume that everyone knows what "DS" means.
• greybeard: Please compare your algorithm to selection sort.

Answer 1

The design makes no sense in terms of Object-Oriented principles:

1. The inheritance relation between the two classes makes no logical sense. It seems to serve the sole purpose of sharing the scanner instance. Inheritance is more than mechanism for sharing variables. It has application (aka business) meaning. It defines "is kind of" relationship: a Dog is a kind of Animal.

2. The class names say absolutely nothing about what the code does. Well, one could argue that Main serves as the program's entry point. I've seen this "naming convention" in actual java projects so that's passable. I would call it something like ArraySorter. It is also acceptable to add the main() method to the other methods instead of putting in a separate class. Methods class is another matter: There has to be better name that describes what the collection of methods do. In conclusion, it is up to you whether PushMaxSorter has its own main() method or keep it separate.

3. So, if we look at Methods as PushMaxSorter that is a class that implements your improved bubble sort algorithm, then getArray() can be regarded as a constructor. and it should take a Scanner instance as argument.

4. So, from the above constructor, we deduce that PushMaxSorter holds the int array as internal data structure. So the sort method should accept no arg and return void and if you wish you can add getArray() that is a "classic" getter method: allows access to the instance variable.

5. regarding printArr(): so we now can deduce that this method also accept no arg. It is considered "best parctice" that a class with a data structure (or just a bunch of variables) will have a string representation of its internal state by overriding Object's toString() method. This allows the caller to conrtol to which output the String is written.

Regarding complexity, I admit this is not my expertise. However, I do not see any signs of exponential iteration on the data structure. Your algorithm may improve upon the performance of classic bubble sort, but complexity is about scaling: comparing the performance of the same algorithm on input that is increasing in size. I'd say complexity here is the same as classic bubble sort, which is O(n^2)

Note: a more robust and extensible design will say that you need to decouple the data structure from the sorting algorithm (much like the Java Collections framework) so that you can apply your improved algorithm not only to array of integers. But I think that is an "advanced" topic that requires deeper study of advanced OO principles.

• SandyG: Thanks a ton Sharon. I surely need to learn design principles and you taught me some.