- Prepare
- Algorithms
- Sorting
- Lily's Homework
- Discussions
Lily's Homework
Lily's Homework
+ 0 comments def lilysHomework(arr): elements = [(value, index) for index, value in enumerate(arr)] sorted_elements = sorted(elements) index_map = {index: i for i, (_, index) in enumerate(sorted_elements)} asc_swaps = calculate_swaps(arr, index_map) sorted_elements = sorted(elements, reverse=True) index_map = {index: i for i, (_, index) in enumerate(sorted_elements)} desc_swaps = calculate_swaps(arr, index_map) return min(asc_swaps, desc_swaps) def calculate_swaps(arr, index_map): swaps = 0 visited = [False] * len(arr) for i in range(len(arr)): if visited[i] or index_map[i] == i: continue cycle_size = 0 j = i while not visited[j]: visited[j] = True j = index_map[j] cycle_size += 1 if cycle_size > 0: swaps += cycle_size - 1 return swaps
+ 1 comment hint: count the number of swap operation needed to sort the given array either in ascending or decenting order. return which one cost less.
+ 0 comments Here is the solution of Lily's Homework Click Here
+ 0 comments Feel free to let me know if there's any issue in this C code.
#define min(x, y) (((x) < (y)) ? (x) : (y)) int comp(const void * a, const void * b){ return *(int*)a-*(int*)b; } int no_of_swaps(int *arr,int arr_count){ int *a = (int*)malloc(arr_count*sizeof(int)); int* sort; int i,c=0; for(i=0;i<arr_count;i++){ a[i] = arr[i]; } qsort(a,arr_count,sizeof(int),comp); for(i=0;i<arr_count;i++){ if(arr[i] != a[i]){ c +=1; int j = i+1; while(arr[j] != a[i]){ j++; } int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } free(a); return c; } int lilysHomework(int arr_count, int* arr) { int *arr_copy = (int*)malloc(arr_count*sizeof(int)); memcpy(arr_copy, arr, arr_count*sizeof(int)); int normal_order, reverse_order; normal_order = no_of_swaps(arr_copy,arr_count); int* reversed_arr = (int*)malloc(arr_count*sizeof(int)); for (int i = 0; i < arr_count; i++) { reversed_arr[i] = arr[arr_count - i - 1]; } reverse_order = no_of_swaps(reversed_arr,arr_count); return min(normal_order,reverse_order); }
+ 1 comment It takes me lots of time to solve this challenge, so I have to write something to share with you bothered by it:
a. ascending and descending sequence of the data will influence the swap times. So your method needs to be called twice and then you choose the smaller swap times as your answer. b. Consider the small circles of data, which might affect the swap times. for example, 0>2, 2>1, 1>0, 3->4, 4>5, 5>3, totally there are 4 swaps, but my first try uses another simple method which gets 5 swaps and that is wrong.
Sort 247 Discussions, By:
Please Login in order to post a comment