역순수를 계산하다
3776 단어 병합 정렬
#-*- coding:utf-8 -*-
#import pdb
def sort_count(data):
"""
using merge sort and count inversion
"""
global count
count = 0
def merge_sort(data):
global count
if len(data)<2:
return data
left = merge_sort(data[:(len(data)//2)])
right = merge_sort(data[(len(data)//2):])
idx_left = idx_right = 0
result = []
while idx_left < len(left) and idx_right < len(right):
if left[idx_left] <= right[idx_right]:
result.append(left[idx_left])
idx_left += 1
else:
result.append(right[idx_right])
idx_right += 1
count += len(left)-idx_left
while idx_left < len(left):
result.append(left[idx_left])
idx_left += 1
while idx_right < len(right):
result.append(right[idx_right])
idx_right += 1
return result
sorted_data = merge_sort(data)
return count
class Ivrs_num(object):
def __init__(self, filename):
self.count = 0
self.filename = filename
def inverse_count(self):
data = self.load_txt()
def merge_sort(data):
if len(data)<2:
return data
left = merge_sort(data[:(len(data)//2)])
right = merge_sort(data[(len(data)//2):])
idx_left = idx_right = 0
result = []
while idx_left < len(left) and idx_right < len(right):
if left[idx_left] <= right[idx_right]:
result.append(left[idx_left])
idx_left += 1
else:
result.append(right[idx_right])
idx_right += 1
self.count += len(left)-idx_left
while idx_left < len(left):
result.append(left[idx_left])
idx_left += 1
while idx_right < len(right):
result.append(right[idx_right])
idx_right += 1
return result
merge_sort(data)
return self.count
def load_txt(self):
int_list = []
with open(self.filename) as f:
for line in f:
int_list.append(int(line))
return int_list
if __name__ == '__main__':
m = Ivrs_num('IntegerArray.txt')
print(m.inverse_count())
cpp 버전:
#include <iostream>
//Inversion Pair
int merge_sort(int a[], int len)
{
if(len<2) return 0;
int left[len/2],right[len-len/2];
int i,j,index,inver=0;
for(i=0;i<len/2;i++)
{
left[i]=a[i];
}
for(i=len/2,j=0;i<len;i++,j++)
{
right[j]=a[i];
}
inver += merge_sort(left, len/2);
inver += merge_sort(right, len-len/2);
index=0;
i=0;
j=0;
while(i<len/2 && j<(len-len/2))
{
if(left[i] <= right[j])
{
a[index]=left[i];
index++;
i++;
}
else
{
a[index]=right[j];
j++;
index++;
inver += len/2 - i;
}
}
while(i<len/2)
{
a[index]=left[i];
index++;
i++;
}
while(j<(len-len/2))
{
a[index]=right[j];
index++;
j++;
}
return inver;
}
int main()
{
int len;
std::cin>>len;
int array[len],i;
for(i=0;i<len;i++)
{
std::cin>>array[i];
}
std::cout<<merge_sort(array,len);
/*
int array[]={4,2,6,1,5,3,0};
int count=0;
std::cout<<merge_sort(array,7)<<std::endl;
int i=0;
for(i=0;i<7;i++)
{
std::cout<<array[i]<<" ";
}
*/
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 정렬 알고리즘 요약 병합 정렬병합 조작(merge)은 병합 알고리즘이라고도 하는데 이미 정렬된 두 서열을 하나의 서열로 합친 조작을 가리킨다.빠른 정렬과 유사하게 자바에서 통합된 것을 살펴봅시다. 병합 정렬(Merge)은 두 개 이상의 순서표를...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.