thugwaffle I think this is a bit too easy to classify as "Medium", especially since you not only give most of the code in the question, but the solution too!
levanlevi absolutely! WHY?..
MobilityWins what language were you using, cuz in C# it wasnt easy for me since there are no built in functions for Swap
levanlevi but swap is fairly easy to implement yrself?..
MobilityWins to be honest, no because I'm kind of brand new to the different sorts. I tried copying the for loops and then changing swap(a[j], a[j + 1]); to a[j] = a[j+1];
but i dont think that works and im away from the computer right now to test it
d_koudinov [deleted]l_mohamed_157 i agree with you even if you try to implement the Swap method as follow Swap (ref int a , ref int b) { int temp; temp = b; b = a; a = temp; } the compiler of hacker rank did not recoginze the ref keywork which refers to pass by refernce
levanlevi So difficulty of the problem reduces to the difficulty of swap :)) you don't need "ref" in c# - array keeps references by default
mihir7759 there are no built in function for the swaps in C also
amrkhaledccd This should be classified as easy. The fact it is marked as Medium made me think 100 times before submitting my solution, i thought there is something i didn't understand
adilek Mine passed from 1st attempt. However, I still think there is something I did not understand.
X1011 fun fact: you don't need to actually perform the bubble sort to find the total number of swaps necessary; you can just count the inversions, as in the problem Merge Sort: Counting Inversions. not that it would be easier to code, but it would have lower time complexity.
louis_grimaldi True. Count the inversions, and then iterate once through the array to find the minimum and maximum value (in the end the first and last element as the array is sorted). O(n^2) -> O(n).
siebenschlaefer Can you really count the inversions in O(n)?
MaxNRG Python 3 solution:
n = int(input().strip()) a = list(map(int, input().strip().split(' '))) numSwaps = 0 while True: SwapsFlag = False for i in range(len(a)-1): if a[i] > a[i+1]: a[i], a[i+1] = a[i+1], a[i] numSwaps += 1 SwapsFlag = True if not SwapsFlag: break print('Array is sorted in', numSwaps, 'swaps.') print('First Element:', a[0]) print('Last Element:', a[-1])
mspagon a[i], a[i+1] = a[i+1], a[i]
Could you explain this line please?
EDIT: Answer is here
https://codeandchaos.wordpress.com/2014/11/15/swap-two-objects-in-python/
joshiii swapping of elements in python 3
weldon_thomas Interesting implementation. So best case O(N), worst case still O(N^2)?
randa_el_mrabet1 Yes :)
joshiii how can you apply loop in first two lines
gleventhal I did basically the same algo. I don't understand how some solutions seem to just be doing a single loop without being wrapped in a while True, that wouldn't result in a sorted list for many situations, like if the lowest number is last in the list. Maybe I am missing something.
alvinpon I can't believe that the level of this question is medium.
kakyoin01 This is an odd problem. It tries to provide a foundation for learning the ins and outs of bubble sort by giving the basic algorithm and asking for metrics around it, but I think it would have been better to supply a general description of the bubble sort algorithm's behavior instead of flat-out give the algorithm in the problem. As it stands now, this feels more like an algorithm highlight exercise rather than an exercise in implementing/learning the algorithm. I guess since this used to be classified as a Medium difficulty problem, there was some problem trying to balance it for Easy difficulty...
suribabubonu399 i didn't find any difficulty while solving this problem!!
nyhack56 C#:
Passed all test cases:
static void countSwaps(int[] a) { int max = a.Max(); int min = a.Min(); int temp = 0; int swaps = 0; for (int x = 0; x < a.Length; x++) { for (int y = 0; y < a.Length - 1; y++) { if (a[y] > a[y + 1]) { temp = a[y]; a[y] = a[y + 1]; a[y + 1] = temp; swaps++; } } } Console.WriteLine("Array is sorted in {0} swaps.", swaps); Console.WriteLine("First Element: {0}", min); Console.WriteLine("Last Element: {0}", max); }
acfromspace My Python3 solution:
def countSwaps(a): swaps = 0 for check in a: for counter in range(len(a)-1): if a[counter] > a[counter+1]: temp = a[counter+1] a[counter+1] = a[counter] a[counter] = temp swaps += 1 return print("Array is sorted in %i swaps.\nFirst Element: %i\nLast Element: %i" % (swaps, a[0], a[-1]))
To build on this, I'm sure there's a library to swap easier or a different implementation of it.
orskaya C#
var n = a.Length; var swaps = 0; for (var i = 0; i < n; i++) { for (var j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { var tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; swaps++; } } } Console.WriteLine("Array is sorted in {0} swaps.", swaps); Console.WriteLine("First Element: {0}", a[0]); Console.WriteLine("Last Element: {0}", a[n - 1]);
Sort 140 Discussions, By:
Please Login in order to post a comment