Thread replies: 13
Thread images: 1
Thread images: 1
File: Untitled.png (6KB, 631x543px) Image search:
[Google]
6KB, 631x543px
hey /sci/
I created a sort algorithm and am wondering if there are ways in math to prove if a specific algorithm is performed, that a list afterwards will have a specific property.
For my specific case let's say given a list (x_1, x_2,...,x_n) of un-ordered elements, I want to sort them into a new list of (y_1, y_2,...y_n) elements such that the new list has the property y_1 <= y_2 <= ... <= y_n.
The algorithm I used is this:
for (i=0;i<n-1;i++)
{
for (j=0;j<n-1;j++)
{
if (x_i <= x_i+1)
{
temporary = x_i
x_i = x_i+1
x_i+1 = temporary
}
}
}
Again, is there a way to directly prove like by induction or by cases that when an algorithm is performed a new set will have a specific property?
pic unrelated but lols
>>
>>8212192
The usual trick is to generalize the hypothesis so that it gives you a correct statement about the list at every step of your algorithm. Then do induction over the steps in the algorithm.
>>
>>8212211
Or to be more specific to this case, the hypothesis should be something like "at step i, this part of the list is sorted."
>>
OP, what you "created" is known as the bubble sort algorithm and it's the most basic one there is.
Although I'm also curious about proving the correctness of this algorithm.
Have you considered using Hare's logic to do it?
The book "Systematic Programming: An Introduction" by Niklaus Wirth may help you with that.
>>
>>8212222
what do you mean Hare's logic? few quick googles and can't find anything
I'll look up that book now thank you
>>
>>8212222
>OP, what you "created" is known as the bubble sort algorithm and it's the most basic one there is.
A standard bubble sort would not have his outer "for" loop, but instead would have a while loop that used a boolean variable to detect if the sort was done.
swapped = 1
while swapped == 1 {
swapped = 0
for (j=0;j<n-1;j++) {
if (x_i <= x_i+1) {
swapped = 1
temporary = x_i
x_i = x_i+1
x_i+1 = temporary
}
}
}
>>
>>8212222
Also, I just looked up bubble sort and it is a little different. Bubble sort runs until the list is sorted, which may actually be better conditions than the code above. What I wrote loops (n-1)^2 times which may actually be the maximum number of loops needed to fully sort in this way... this could be a neat proof too.
>>
>>8212192
Still my favorite sort:
https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
>>
>>8212253
i'm a noob but this is fascinating can u explain what is going on here?
>>
>>
>>8212262
Yeah sure.
Each item gets assigned a thread and a task.
Each task waits a time proportional to its value before it appends to the end of a list.
>>
>>8212192
>if (x_i <= x_i+1)
You want x[j]>x[j+1] or "not (x[j] <= x[j+1])"
>Again, is there a way to directly prove like by induction or by cases that when an algorithm is performed a new set will have a specific property?
Yes
>Lemma: for the i-th loop the inner loop bring the i+1-th largest element to its place
>Proof: induction
>>
>>8212192
Floyd, Robert W., “Assigning meanings to programs,” Proceedings of Symposia in Applied Mathematics, Vol. 19 (1967), pages 19–32.
http://www.eecs.berkeley.edu/~necula/Papers/FloydMeaning.pdf
Hoare, C. A. R., “An axiomatic basis for computer programming,” Communications of the ACM, Vol. 12, No. 10 (1969), pages 576–583.
https://www.cs.cmu.edu/~crary/819-f09/Hoare69.pdf
Hoare, C. A. R., “Proof of a Program: FIND,” Communications of the ACM, Vol. 14 (Jan. 1971), Pages 39-45.
https://www.cs.cmu.edu/~crary/819-f09/Hoare71.pdf
Thread posts: 13
Thread images: 1
Thread images: 1