My retarded idea

[323]

Don't even ask...

In theory, I'm trying to create the most inefficient sorting algorithm of all time.

Why? I'm bored and don't feel like doing my comp sci homework where we're supposed to use the MOST efficient sorting algorithm we can find.

Anyway, here's my code. I know it's really messy right now and can be made into much less lines of code and such, but I wrote this pretty late at night, so I'll just update it whenever I get the chance. Also pushing to github whenever I get it set up on this computer, lol.

What it does RIGHT NOW:

Right now, it only checks the first number, but this is how it works:

Compare the first number to the second number. Are they equal? If so, compare the first number to the third number. If they aren't, randomize the entire array and start over.

import java.util.*;

class EfficientSort
{
    public static void main(String[] args)
    {
        //Print title and stuff
        System.out.println("This is EfficientSort, made by 323.");
        //Initialize Random Num Gen
        Random rgen = new Random();
        //Initialize array
        int[] numbers = new int[11];
        //Populate array with 0-10
        for (int i=0; i<numbers.length; i++) 
        {
            numbers[i] = i;
        }
        //Print original array before randomization
        System.out.println("Original array:");
        for (int z=0; z<numbers.length; z++) 
        {
            System.out.print(numbers[z] + ", ");
        }
        //Start new line for next row of numbers
        System.out.println("");
        //Randomize array
        for (int x=0; x<numbers.length; x++) 
        {
            int randomPosition = rgen.nextInt(numbers.length);
            int temp = numbers[x];
            numbers[x] = numbers[randomPosition];
            numbers[randomPosition] = temp;
        }
        //Print array after randomization
        System.out.println("Randomized Array:");
        for (int y=0; y<numbers.length; y++) 
        {
            System.out.print(numbers[y] + ", ");
        }
        //Print starting message
        System.out.println("");
        System.out.println("Beginning sorting algorithm...");
        //Check if the numbers are in the right order
        int r = 0;
        int num = 1;
        while (r == 0) //r only = 1 when entire set is sorted
        {
            while (num<numbers.length)
            {
                if (numbers[0] < numbers[num])
                {
                    num++;
                }
                else
                {
                    //Randomize array
                    for (int x=0; x<numbers.length; x++) 
                    {
                        int randomPosition = rgen.nextInt(numbers.length);
                        int temp = numbers[x];
                        numbers[x] = numbers[randomPosition];
                        numbers[randomPosition] = temp;
                    }
                    for (int z=0; z<numbers.length; z++) 
                    {
                        System.out.print(numbers[z] + ", ");
                    }
                    System.out.println("");
                }
            }
            System.out.println("");
            System.out.println("Sorted First Number!");
            System.out.println("First Number Sorted Array");
            for (int z=0; z<numbers.length; z++) 
            {
                System.out.print(numbers[z] + ", ");
            }
            r = 1;
        }
    }
}

Questions? Comments? Suggestions? Criticism? All are welcome.

[The Unintelligible]

Ok.

[GAMEchief]

var a = [5, 4, 3, 2, 1],
  sort = function(a)
  {
    var e = a.length;
    for (var x = 0; x < e - 1; x++)
    {
      if (a[x] > a[x + 1])
      {
        var n = [];
        for (var y = 0; y < e; y++)
          n.push(a[Math.random() < 0.5 ? "pop" : "shift"]());
        return sort(n);
      }
    }
    return a;
  };
alert(sort(a));

ez

[Isonyx]

Neat code, think psuedorandom numbers is definitely the way to go.
Can it have external unrelated road blocks added, such as overflows and unnecessarily taking up excess memory?

[323]

Neat code, think psuedorandom numbers is definitely the way to go.
Can it have external unrelated road blocks added, such as overflows and unnecessarily taking up excess memory?

Ooh, that's a really good idea. I think I'll try to add that, random memory leaks and stuff haha. Or maybe every time it's randomized, it's stored in ANOTHER array, causing a huge number of arrays to be created, and thus a huge amount of memory being used.

var a = [5, 4, 3, 2, 1],
  sort = function(a)
  {
    var e = a.length;
    for (var x = 0; x < e - 1; x++)
    {
      if (a[x] > a[x + 1])
      {
        var n = [];
        for (var y = 0; y < e; y++)
          n.push(a[Math.random() < 0.5 ? "pop" : "shift"]());
        return sort(n);
      }
    }
    return a;
  };
alert(sort(a));

ez

Yeah, a lot easier when you're not trying to use Java, haha. Nice code though.

[GAMEchief]

Yeah, a lot easier when you're not trying to use Java, haha. Nice code though.

I was surprised it worked. Second try, because I forgot a.length gets reparsed each loop, so I had to define it as e.
It was also surprisingly fast, but I guess I always forget to give JavaScript credit for how fast it is in Chrome.

[323]

I was surprised it worked. Second try, because I forgot a.length gets reparsed each loop, so I had to define it as e.
It was also surprisingly fast, but I guess I always forget to give JavaScript credit for how fast it is in Chrome.

Or maybe the browser doesn't have a good randomize function o: I've heard of that being a problem in some browsers.

Also, updated code with some bugfixes, fixed first number discovery. Moving on to second number.

EDIT: Got it to calculate the first number, super easy because the chances are 1 in 10. Now attempting the second number, it's been on for an hour, still no results hahahaha. I guess the chances of getting an array starting with 0, 1 are insanely small.

[GAMEchief]

What?

Are you trying to randomly generate an array [1, 2, 3, 4, ...]?

[323]

What?

Are you trying to randomly generate an array [1, 2, 3, 4, ...]?

So, you start with an array

numbers[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

Then, it puts it into a random order.

Then, it checks to see if it's in the right order.

If even one number is out of order, it will re-shuffle the array and start over.

I based it off of the BogoSort algorithm, but I'm going to try to add more horrible slowness to make it an even more inefficient sorting algorithm, haha.

[Riddle]

I was going to recommend the BogoSort, but it seems like that was the motivation for your algorithm. XD

You should look into Statistics. You can actually calculate the percentage of success of your algorithm, since it is random. From memory, I believe you multiply the chance percent of each number being in the right position... so: for an array of length 10, you would have 1/10 chance to get 1 number in its rightful position, therefore 1/100 to get 2 numbers in the right position... and so on. So for 10 numbers, you would have a 1/(10^10) chance of getting them all in order! Of course computers do not generate completely random numbers, so it is more or less an approximation of your success chance.

I may be completely incorrect on how to calculate the success chance, it's been a couple of years since I've actually had a math class or had to use statistics.

[323]

I was going to recommend the BogoSort, but it seems like that was the motivation for your algorithm. XD

You should look into Statistics. You can actually calculate the percentage of success of your algorithm, since it is random. From memory, I believe you multiply the chance percent of each number being in the right position... so: for an array of length 10, you would have 1/10 chance to get 1 number in its rightful position, therefore 1/100 to get 2 numbers in the right position... and so on. So for 10 numbers, you would have a 1/(10^10) chance of getting them all in order! Of course computers do not generate completely random numbers, so it is more or less an approximation of your success chance.

I may be completely incorrect on how to calculate the success chance, it's been a couple of years since I've actually had a math class or had to use statistics.

Oh cool, thanks for the information, haha.

Also, put it on my github, check it out here: http://github.com/323

[GAMEchief]

I was going to recommend the BogoSort, but it seems like that was the motivation for your algorithm. XD

You should look into Statistics. You can actually calculate the percentage of success of your algorithm, since it is random. From memory, I believe you multiply the chance percent of each number being in the right position... so: for an array of length 10, you would have 1/10 chance to get 1 number in its rightful position, therefore 1/100 to get 2 numbers in the right position... and so on. So for 10 numbers, you would have a 1/(10^10) chance of getting them all in order! Of course computers do not generate completely random numbers, so it is more or less an approximation of your success chance.

I may be completely incorrect on how to calculate the success chance, it's been a couple of years since I've actually had a math class or had to use statistics.

You're a little off.

Since the first number is correct (1/10 chance), then the second number has a 1/9 chance of being correct (since the first number is no longer in the pool of numbers). And the third, 1/8, and so on and so forth.

So the odds are 1/(10!) or 1 in 10 factorial.

[323]

You're a little off.

Since the first number is correct (1/10 chance), then the second number has a 1/9 chance of being correct (since the first number is no longer in the pool of numbers). And the third, 1/8, and so on and so forth.

So the odds are 1/(10!) or 1 in 10 factorial.

Oh cool, thanks for the clarification. And 10 factorial = 3628800, so there's a 1/3,628,800 chance of getting all of the numbers correct. Now I just need to figure out how many tries it does a second, and then I can figure out about how long it takes. I think in the final version of this I'm going to use a set of 100 numbers though, haha.

[GAMEchief]

Tries it does a second?

Why not just time how long it takes to complete...?

startTime = currentTimeWithMilliseconds();
doSort();
endTime = currentTimeWithMilliseconds();
total = endTime - startTime;

[323]

Tries it does a second?

Why not just time how long it takes to complete...?

startTime = currentTimeWithMilliseconds();
doSort();
endTime = currentTimeWithMilliseconds();
total = endTime - startTime;

Because sorting algorithms like bogosort can take years. One of 'em takes longer than the heat death of the universe.

[GAMEchief]

That again depends on the length of the array being sorted, and as stated, even pure randomness has a limit to how many iterations it would take. 1 in 3 million would not take until the heat death of the universe.

[Riddle]

You're a little off.

Since the first number is correct (1/10 chance), then the second number has a 1/9 chance of being correct (since the first number is no longer in the pool of numbers). And the third, 1/8, and so on and so forth.

So the odds are 1/(10!) or 1 in 10 factorial.

Oh, you're right! I thought there was something iffy in my solution. Silly me, I'm too old to remember stuff anymore.

That again depends on the length of the array being sorted, and as stated, even pure randomness has a limit to how many iterations it would take. 1 in 3 million would not take until the heat death of the universe.

Well, you have 1/3M chance to get the sort right, every time you sort. So it is possible that you will never get a sorted array! EVER! The chances of that happening are slim, as time goes to infinity... but it could still happen!

[GAMEchief]

Right, but the average length of a calculation wouldn't nearly be the heat death of the universe. To generate a ten digit number. Especially if any two or more digits are the same.

[Riddle]

Of course not! Especially not in computers, which cannot generate completely random numbers.

[The Unintelligible]

Of course not! Especially not in computers, which cannot generate completely random numbers.

Nothing can generate completely random numbers. Nothing is truly random. Technically they're called pseudo random numbers.

[Isonyx]

Nothing can generate completely random numbers. Nothing is truly random. Technically they're called pseudo random numbers.

quantum entanglement?

[The Unintelligible]

Not sure if you can technically call anything genuinely "random." I don't know about quantum entanglement in particular, but almost everything has a clause or offset.

[Isonyx]

Not sure if you can technically call anything genuinely "random." I don't know about quantum entanglement in particular, but almost everything has a clause or offset.

bro bro. quantum entanglement is an exception from what I've read.
the micro behavior of atoms and such seems to constitute as the only truly random occurrences we can observe

[Riddle]

bro bro. quantum entanglement is an exception from what I've read.
the micro behavior of atoms and such seems to constitute as the only truly random occurrences we can observe

Would that mean that Quantum Computers will be able to produce genuinely random numbers?

[Artificial]

No. Even with quantum entanglement, we don't know enough about any of it yet. When we get down to a quantum level, many things appear to be random, but there are often statistical models at work behind the scenes.

[SpornyTheAlien]

Give the program to a toddler once you are finished and watch it go nuts.

[Tree]

No. Even with quantum entanglement, we don't know enough about any of it yet. When we get down to a quantum level, many things appear to be random, but there are often statistical models at work behind the scenes.

Thus why most things refer to it as pseudo-random.